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:
def traverse(node):
"""
>>> node1=Node(1)
>>> node2=Node(2)
>>> node3=Node(3,node1,node2)
>>> node4=Node(4)
>>> node5=Node(5,node3,node4)
>>> traverse(node5)
5
3
1
2
4
"""
if node==None: return
print node.value
traverse(node.left)
traverse(node.right)
class Node:
def __init__(self,value,left=None,right=None):
self.value=value;self.left=left;self.right=right
import doctest
doctest.testmod()
A little trickier is an implementation without recursion:
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=[]
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
import doctest
doctest.testmod()
The Python example here is complete, and looks much better, no doubt! But I have a question: How different is it from the book anyway? They haven’t bothered about the stack implementation there, whereas you have implemented the stack (and named it Lifo). Just curious…
Srikanth – thanks for posting… unfortunately I lent away the book and can’t remember their implementation, but I do remember it was pretty convoluted and thinking as I read through it how much simpler the stack I’d put in made it.
Thank you for posting your python implementations.
Your solution is better than from the book. But if you use list as a stack, it’s even simpler. You don’t need to write your own LIFO class anymore.
The modified code is attached:
#! /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
“””
Thanks Betty – that’s good to know – I put your code in the post above.