import Queue
import pdb

class BinTree:

    val = 0
    left = None
    right = None

    def __init__(self,_val):
        self.val = _val
        self.left = None
        self.right = None

def createBTNode(val):
	return BinTree(val)



def arr_to_btree(input_array):

	i = 0
	root = createBTNode(input_array[0])
	node_queue = Queue.Queue(maxsize=100)
	node_queue.put(root)

	while not node_queue.empty():
		new_tree = node_queue.get()

		if 2*i+1 >= len(input_array):
			break

		left_node = createBTNode(input_array[2*i+1])
		new_tree.left = left_node
		node_queue.put(left_node)

		if 2*i+2 >= len(input_array) or input_array[2*i+1] is None:
			break
		right_node = createBTNode(input_array[2*i+2])
		new_tree.right = right_node

		if input_array[2*i+2] is not None:
			node_queue.put(right_node)
		i+=1
	return root



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


def main():
	arr = [2,3,6,None,8,2,3,3,1]
	pdb.set_trace()
	root = arr_to_btree(arr)
	print_tree(root)


main()