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]] 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.
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) 
[A,B,E,F], though? F isn't a descendant of E or vice versa. If you're not iterating over all possible root-to-leaf paths, can you give more detail about what you are trying to do?