CODEWITHSUNDEEP
pythonalgorithmtree
Jozef
Jozef

Reputation: 41

Tree traversal recursion

I am new to programming. I am working on my project of tree

my tree look like this tree structure

I have written code to traverse the complete tree. Currently my traversel will print the complete tree like this A,B,E,F,C,D,G,H,I,J,K

def tree_traversal(self, node):
    if(node != None):
      print node.name
      for child_nodes in node.children:
          self.tree_traversal(child_nodes)

However I want to get the output like this.

[[A,B,E],[A,B,F],[A,C],[A,D,G,H],[A,D,G,I],[A,D,G,J],[A,D,G,K]]

Upvotes: 3

Views: 11092

Answers (2)

vallentin
vallentin

Reputation: 26235

Since you didn't give any tree/node class, I made one to test with:

class Node:
    def __init__(self, data, children=None):
        if children is None:
            children = []
        self.data = data
        self.children = children

    def __str__(self):
        return str(self.data)

    __repr__ = __str__

The tree extracted from your image:

tree = Node("A", [
    Node("B", [
        Node("E"),
        Node("F"),
    ]),
    Node("C"),
    Node("D", [
        Node("G", [
            Node("H"),
            Node("I"),
            Node("J"),
            Node("K"),
        ])
    ])
])

What you want is an algorithm that can get all possible root to leaf paths.

def get_all_paths(node, path=None):
    paths = []
    if path is None:
        path = []
    path.append(node)
    if node.children:
        for child in node.children:
            paths.extend(get_all_paths(child, path[:]))
    else:
        paths.append(path)
    return paths

Testing it yields the output you wished for:

paths = get_all_paths(tree)
print(paths)
# Prints:
# [[A, B, E], [A, B, F], [A, C], [A, D, G, H], [A, D, G, I], [A, D, G, J], [A, D, G, K]]

However note that [A,B,E,F] is not a valid path, as F is not a child of E. So I assume this was a mistake.

Upvotes: 4

Bobby
Bobby

Reputation: 1571

You basically want to print all the path from the root. You can do this recursively by passing the current path through.

The base case will be when the traversal hits a leaf node, concatenate the leaf node to the path and print or do whatever you want.

presudo code:

def traverse(node, path):
    if node is None:
        return
    if node.left == None and node.right == None:
        doStuff(path + node.data)
        return
    else:
        traverse(node.left, path + node.data)
        traverse(node.right, path + node.data)

Upvotes: 3

Related Questions