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