Rebrained!

Tree Traversal – Python

Another question posed in the Programming Interviews Exposed book. A pre-ordered traversal of a binary tree (counterclockwise starting at root, printing nodes as you encounter them) is pretty straight forward, and a very natural thing to implement with recursion:

>>> class Node:
	def __init__(self,value,left=None,right=None):
		self.value=value;self.left=left;self.right=right

>>> node1=Node(1)
>>> node2=Node(2)
>>> node3=Node(3,node1,node2)
>>> node4=Node(4)
>>> node5=Node(5,node3,node4)

>>> def traverse(node):
	if node==None: return
	print node.value
	traverse(node.left)
	traverse(node.right)

>>> traverse(node5)
5
3
1
2
4
>>>

The trick is how to implement this without recursion – thinking caps on! Well, using a stack may be the best way (see earlier post), though it’s amazing how much more convoluted it gets. I’m sure it can be done more efficiently, though I like my algorithm better than the one in the book. Anyone have something better?

def treeWalker(node):
    """
    >>> node1=Node(1)
    >>> node2=Node(2)
    >>> node3=Node(3,node1,node2)
    >>> node4=Node(4)
    >>> node5=Node(5,node3,node4)
    >>> treeWalker(node5)
    5
    3
    1
    2
    4
    >>>
    """
    lifo=Lifo()
    while True:
        print node.value
        if node.left!=None:
            lifo.push(node)
            node=node.left
        else:
            node=lifo.pop()
            if node==None: return
            node=node.right

class Node:
    def __init__(self,value,left=None,right=None):
    	self.value=value;self.left=left;self.right=right

class Lifo:
    def __init__(self):
        self.lifo = ()
    def push(self, data):
        self.lifo = (data, self.lifo)
    def pop(self):
        if len(self.lifo)==0: return None
        ret, self.lifo = self.lifo
        return ret

if __name__ == "__main__":
    import doctest
    doctest.testmod()

EDIT 5/15/2010 – Thanks Betty for the simplication below…

#! /usr/bin/python

def treeWalker(node):
    lifo=[]
    while True:
        print node.value
        if node.left!=None:
            lifo.append(node)
            node=node.left
        else:
            try:
                node=lifo.pop()
            except:
                return None
            node=node.right

class Node:
    def __init__(self, value, left=None, right=None):
        self.value=value;self.left=left;self.right=right

if __name__ == "__main__":
    n1=Node(1)
    n2=Node(2)
    n3=Node(3,n1,n2)
    n4=Node(4)
    n5=Node(5,n3,n4)
    treeWalker(n5)

    """
    Result:
        5
        3
        1
        2
        4
        """