Just a small exercise to myself how to traverse trees in Python. In this post - classic example with recursion.
So we have a simple tree structure below with some data filled in.
class TreeNode(object): def __init__(self, name): self.children = list() self.name = name root = TreeNode("Root") root.children.extend( (TreeNode("Fruits"), TreeNode("Berries")) ) root.children.children.extend( (TreeNode("Apple"), TreeNode("Peach")) ) root.children.children.extend( (TreeNode("Cherry"), TreeNode("Mullberry")) )The task: Find all paths of the tree from root to leafs.
Classic recursion solution
import copy def traverse_recursive(node, path=list(), pathes=list()): p = copy.deepcopy(path) p.append(node.name) pathes.append(p) for n in node.children: pathes = traverse_recursive(n, p, pathes) return pathes
Lets use it:
for path in traverse_recursive(root): print pathWhich will print:
['Root'] ['Root', 'Fruits'] ['Root', 'Fruits', 'Apple'] ['Root', 'Fruits', 'Peach'] ['Root', 'Berries'] ['Root', 'Berries', 'Cherry'] ['Root', 'Berries', 'Mullberry']
- Classic algorithm. Any computer science student can write this
- The code looks almost the same on any language
- Recursion. On very deep trees one may have to change Python's max execution depth.
- All found paths are accumulated in memory before returned to the caller. Can really bloat memory on large trees.