Monday, August 13, 2012

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(nlog n). O(log n) for recursion depth, plus O(nlog 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.