'''Create a binary tree from an input list.'''
import math
# If we store a full binary tree using BFS into a list, map the index of the
# node to its parent and which branch this node is.
# node_index parent_index branch
# 1 0 0
# 2 0 1
# 3 1 0
# 4 1 1
# 5 2 0
# ...
def GetParentMap(max_nodes):
parent_map = {} # index: (parent_index, left_or_right)
current_parent = 0
current_branch = 0
for i in range(1, max_nodes):
parent_map[i] = (current_parent, current_branch)
# Switch between left and right
current_branch = 1 - current_branch # left: 0, right: 1
if current_branch == 0:
current_parent += 1
return parent_map
def GenerateTree(input_list):
if not input_list:
return None
max_depth = int(math.ceil(math.log(len(input_list)+1 ,2)))
num_nodes = 2**max_depth - 1
parent_map = GetParentMap(num_nodes)
nodes = [None] * num_nodes # Save nodes in a list for accessing
root = {'v': input_list[0]} # v: value, 0: left_child, 1: right_child
nodes[0] = root
for i in range(1, len(input_list)):
if input_list[i] is None:
continue
parent_idx, branch = parent_map[i]
parent = nodes[parent_idx]
new_node = {'v': input_list[i]}
parent[branch] = new_node # Link the child here.
nodes[i] = new_node
return root
# Print the tree using in-order traversal.
# A leaf node will be followed by 'NL NR'.
def PrintTree(node):
if node:
print node['v'],
if 0 in node:
PrintTree(node[0]),
else:
print 'NL', # No left child
if 1 in node:
PrintTree(node[1]),
else:
print 'NR', # No right child
if __name__ == '__main__':
while True:
# Sample input_list: [1, 2, 3, 4, None, 5, 6, None, 8, None, None]
input_list = input("Input the tree: ")
tree = GenerateTree(input_list)
PrintTree(tree)
print
