rendered paste body#!/usr/bin/env python
class Node:
def __init__(self, value):
self.data = value
self.left = None
self.right = None
def addLeftChild(self, Node):
self.left = Node
def addRightChild(self, Node):
self.right = Node
def recInOrder(t):
if t is not None:
recInOrder(t.left)
print t.data
recInOrder(t.right)
# we use a stack of course
def nonRecInOrder(t):
stack = []
curr = t
done = False
while(not done):
if(curr != None):
stack.append(curr)
curr = curr.left
else:
if(not (len(stack) == 0)):
curr = stack.pop()
print curr.data
curr = curr.right
else:
done = True
NodeA = Node("A")
NodeB = Node("B")
NodeC = Node("C")
NodeD = Node("D")
NodeE = Node("E")
NodeF = Node("F")
NodeG = Node("G")
NodeH = Node("H")
NodeI = Node("I")
NodeA.addLeftChild(NodeB)
NodeA.addRightChild(NodeC)
NodeB.addLeftChild(NodeD)
NodeB.addRightChild(NodeE)
NodeD.addLeftChild(NodeF)
NodeD.addRightChild(NodeG)
NodeG.addLeftChild(NodeH)
NodeG.addRightChild(NodeI)
print "Non-Recursive:"
nonRecInOrder(NodeA)
print
print "Recursive:"
recInOrder(NodeA)