#!/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)