Tree traversal - the Python loop

Computer Science states that every recursive function can be reimplemented with just a loop. So how about rewriting the previous recursive example?

Lets recall our data structure first:

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.

The looping solution

def traverse(node):
    to_crawl = deque()
    lastlevel = curlevel = 0
    to_crawl.append((curlevel, node))
    breadcrumb = list()

    while to_crawl:
        curlevel, curnode = to_crawl.popleft()
        while lastlevel and lastlevel >= curlevel:
            breadcrumb.pop()
            lastlevel -= 1
        breadcrumb.append(curnode.name)
        yield breadcrumb
        to_crawl.extendleft([ (curlevel+1, c) for c in curnode.children ])
        lastlevel = curlevel

The idea is to use excellent deque data structure, which can be thought of a list that can be efficiently appended/popped from both left and right.

Again, lets use it:

for breadcrumb in traverse(root):
    print breadcrumb

Which will print:

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

Cautious reader will note that the tree is indeed traversed but in the reversed order. The reason is when one extends the deque from left, and consequently pops out items out (from left again) it creates LIFO order, effectively reversing the children processing order. The fix would be to originally insert the children to deque in the reverse order. So instead of:

to_crawl.extendleft([ (curlevel+1, c) for c in curnode.children ])

we can manually insert children in the reversed order like this:

to_crawl.extendleft([ (curlevel+1, curnode.children[i]) for i in xrange(len(curnode.children)-1, -1, -1) ])

Complexity

Time: O(n) - same as with recursion.

Memory: O(log n)K + O(log n). First O(log n) for recursion depth, second O(log n) path buffer. About K - its an average number of children per node - our crawling buffer holds reference to all of the children for each node we encounter, so we need to account for that.

Advantages
Same as with python recursion solution, but even better - no recursion here.

Disadvantages
The only disadvantage I can spot is the fact that we hold references to the children of the nodes we crawl. On extremely shallow and wide trees this can raise the memory footprint almost to O(n). The recursive solution however would still provide O(log n) in this extreme case.

Tree traversal - the Python recursion

This is the second part of of my tree traversal series. In part I I've went through a classical recursion algorithm, and today I'll rewrite it "in a Python way".

Python recursion solution

Given the same tree structure as in part I:

def traverse_recursive(node, path=list()):
    path.append(node.name)
    yield path
    for n in node.children:
        for path in traverse_recursive(n, path):
            yield path
    if path:
        path.pop()

The key approach is to use python yield statement, which makes this function a generator. Here is in depth guide to generators, but in a nutshell, when python runs function which "yield"s instead of returning, two things happen:

• When function is called, then none of the function code actually executes, just a generator object is returned
• Each time generator object is iterated, function code runs until it yields - then yielded value is returned and function execution paused until the next iterator iteration
• The important thing to note is that all of the function context persists between subsequent iterations

The beauty of this technique is that traversed paths are returned to the caller as soon as they are found. Additionally, if caller wants to pause parsing of tree paths, tree traversal pauses as well. Caller can even delegate results processing to another function at some later stage by simply passing generator object over.

Complexity

Time: O(n) - same as with classic recursion.

Memory: O(log n) + O(log n). First O(log n) for recursion depth, second O(log n) path buffer.

Advantages

• Low memory footprint
• Results are available immediately
• Tree is traversed "as you(caller) go". Traversal can be paused/aborted any time.

Disadvantages

• Recursion. On very deep trees one may have to change Python's max execution depth

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.