Tree traversal - the classic recursion

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[0].children.extend( (TreeNode("Apple"), TreeNode("Peach")) )
root.children[1].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 path

Which will print:

['Root']
['Root', 'Fruits']
['Root', 'Fruits', 'Apple']
['Root', 'Fruits', 'Peach']
['Root', 'Berries']
['Root', 'Berries', 'Cherry']
['Root', 'Berries', 'Mullberry']

Complexity

Time: O(n)
Memory: O(log n) + O(n^{log n}). O(log n) for recursion depth, plus O(n^{log n}) since all paths the function returns are pre-buffered during tree traversal.

Advantages

• Classic algorithm. Any computer science student can write this
• The code looks almost the same on any language

Disadvantages

• 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.