bst.py

class Node:
	def __init__(self, v=None):
		self.val = v
		self.left = None
		self.right = None

class BST:
	def __init__(self):
		self.top = Node();

	def add(self, val):
	  self.add_helper(self.top, val)
		# if self.top is None:
		# 	self.top.val = val
		# elif self.top.val > val:
		# 	# traverse left
		# 	if self.top.left is None:
		# 		# vacant spot
		# 		self.top.left = Node(val)
		# 	else:
		# 		self.add_helper(self.top.left, val)
		# else:
		# 	# traverse right
		# 	if self.top.right is None:
		# 		self.top.right = Node(val)
		# 	else:
		# 		self.add_helper(self.top.right, val)

	def add_helper(self, cur, val):
		if cur.val is None:
			cur.val = val
		elif cur.val < val:
			#traverse left
			if cur.left is None:
				cur.left = Node(val)
			else:
				self.add_helper(cur.left, val)
		else:
			if cur.val < val:
			#traverse right
				if cur.right is None:
					cur.right = Node(val)
				else:
					self.add_helper(cur.right, val)

	def print_bst(self):
		# print level wise
		END = Node(-1)
		p_list = []
		p_list.append(self.top);
		p_list.append(END)
		while(len(p_list) != 0):
			cur = p_list[0]
			p_list = p_list[1:]
			if cur == END:
				print("*****")
				continue
			print(cur.val)
			if not cur.left is None:
				p_list.append(cur.left)
			if not cur.right is None:
				p_list.append(cur.right)


def run():
	bst = BST()
	#bst.print_bst()
	bst.add(2)
	bst.print_bst()
	bst.add(1)
	bst.print_bst()
	bst.add(3)
	bst.print_bst()

if __name__ == "__main__":
	run()