#!/usr/bin/python

class node:
	# A simple binary tree class.

	left = None
	right = None
	value = None

	# This class doesn't have to be a binary search tree at all, but
	# binary search trees are a quick way to build a tree to experiment
	# with without too much work.  (In particular, the traversal
	# implementations don't care whether the tree is a binary search
	# tree or any other kind of tree.)
	def search_tree_add(self, new_value):
		if self.value == None:
			self.value = new_value
		elif new_value < self.value:
			if self.left == None:
				self.left = node()
			self.left.search_tree_add(new_value)
		elif new_value >= self.value:
			if self.right == None:
				self.right = node()
			self.right.search_tree_add(new_value)
		else:
			raise "new search tree value can't compare to old"
		return self

def process(n):
	print n.value

# A minimal Python list-based stack implementation
stack = []

def empty():
	if stack == []:
		return 1
	else:
		return 0

def push(a):
	stack.append(a)

def pop():
	return stack.pop()

def recursive_traverse_inorder(some_node):
	if some_node != None:
		recursive_traverse_inorder(some_node.left)
		process(some_node)
		recursive_traverse_inorder(some_node.right)

def iterative_traverse_inorder(n):
	# Store pending actions on the stack as tuples, either
	#	("traverse", node)
	# for a node which should be traversed, or
	#	("process", node)
	# for a node which should be processed.

	push(("traverse", n))
	while not empty():
		t, n = pop()
		if t == "traverse":
			# Replace ("traverse", node) with the sequence of actions
			# constituting a traversal of node -- pushed in reverse inorder.
			if (n.right != None):
				push(("traverse", n.right))
			push(("process", n))
			if (n.left != None):
				push(("traverse", n.left))
		elif t == "process":
			process(n)
		else:
			raise "bad stack action type"

root = node()
root.search_tree_add("hello")
root.search_tree_add("there")
root.search_tree_add("how")
root.search_tree_add("are")
root.search_tree_add("you")
root.search_tree_add("doing")
root.search_tree_add("today?")
root.search_tree_add("this")
root.search_tree_add("tree")
root.search_tree_add("building")
root.search_tree_add("process")
root.search_tree_add("is")
root.search_tree_add("hours")
root.search_tree_add("of")
root.search_tree_add("fun")
root.search_tree_add("for")
root.search_tree_add("the")
root.search_tree_add("whole")
root.search_tree_add("family")