CODEWITHSUNDEEP
pythonrecursiontree
man zet
man zet

Reputation: 901

Python: Get List of all possible path in Tree?

I have a Tree which for example looks like this

 (0, 1)
    (2, 3)
       (4, 5)
          (6, 7)
          (6, 3)
       (4, 1)
          (6, 3)

when i print it with this method:

def deep_print(self, d=0):
    if self == None:
        return

    print("   "*d, self.value)

    for child in self.children:
        child.deep_print(d + 1)

Now i want a method that gives me a list of all possible ways to a leaf. So in this case the output should be:

[[(0,1),(2,3),(4,5),(6,7)], [(0,1),(2,3),(4,5),(6,3)], [(0,1),(2,3),(4,1),(6,3)]]

edit: this is the structure of my tree

class Tree:
    def __init__(self, value, d = 0):
        self.value = value
        self.children = []

    def add_child(self, child):
        self.children.append(child)

    def deep_print(self, d=0):
        if self == None:
            return
        print("   "*d, self.value)
        for child in self.children:
            child.deep_print(d + 1)

Upvotes: 8

Views: 7767

Answers (1)

user2390182
user2390182

Reputation: 73460

A recursive method along the following lines should work:

def paths(self):
    if not self.children:
        return [[self.value]]  # one path: only contains self.value
    paths = []
    for child in self.children:
        for path in child.paths():
            paths.append([self.value] + path)
    return paths

Upvotes: 12

Related Questions