#!/usr/local/bin/python3

import pdb

class node():
	def __init__(self, x , left = None, right = None, parent = None):
		self.val = x
		self.left = left
		self.right = right
		self.parent = parent

def addMe(root, node):
	if root is None:
		return node
	else:
		if node.val < root.val:
			root.left = addMe(root.left, node)
		else:
			root.right = addMe(root.right, node)

	return root

def inorder(root):

	if root is not None:
		inorder(root.left)
		print(root.val)
		inorder(root.right)

def preorder(root):

	if root is not None:
		print(root.val)
		preorder(root.left)
		preorder(root.right)


def postorder(root):

	if root is not None:
		postorder(root.right)
		postorder(root.left)
		print(root.val)

def findTreeHeight(root):
	pass


if __name__ == '__main__':
	root = None

	root = addMe(root,node(10))
	root = addMe(root,node(12))
	root = addMe(root,node(11))
	root = addMe(root,node(13))
	root = addMe(root,node(7))
	root = addMe(root,node(8))
	root = addMe(root,node(5))
	root = addMe(root,node(6))
	root = addMe(root,node(4))



	inorder(root)
	print("#######")
	preorder(root)
	print("#######")
	postorder(root)