#######################- Printing -#################################

import copy
# Check tree
def is_identical_tree_rec(node1, node2):
	if node1 == None and node2 == None:
		return True
	elif node1 != None and node2 != None:
		return ((node1.data == node2.data) and is_identical_tree_rec(node1.left, node2.left) and is_identical_tree_rec(node1.right, node2.right))
	else:
		return False

def is_identical_tree(treeRoot1, treeRoot2):
	return is_identical_tree(treeRoot1, treeRoot2)
	
# TREE TRAVERSAL PRINT CODE
def get_lvl_order(root):
	if (root == None):
		return "None"
	else:
		queue = []
		level_order_list = []

		queue.append(root)
		result = ""
		while (len(queue)):
			temp = queue[0]
			queue.pop(0)

			print("level_order_list: ", level_order_list)
			level_order_list.append(temp.data)
			if (temp.left != None):
				queue.append(temp.left)
    
			if (temp.right != None):
				queue.append(temp.right)
    
		for i in range(len(level_order_list)):
			result += str(level_order_list[i])
			if (i < len(level_order_list) - 1):
				result += ", "
		return result

def get_in_order_rec(node, res):
	if (node == None):
		return res
	else:
		get_in_order_rec(node.left, res)
		res += str(len(res)) + str(node.data) + ", "
		get_in_order_rec(node.right, res)
		return res

def get_in_order(root):
	if (root == None):
		return "None"
	else:
		res = ""
		res += get_in_order_rec(root, res)
		return str(res)

# TREE GRAPIC PRINT CODE

# Display List Code Below:
def height(node):
	if (node == None):
		return 0
	return 1 + max(height(node.left), height(node.right))

def draw_node(output, link_above, node, level, p, link_char):
	if (node == None): 
 		return

	out = "["
	h = len(output)
	SP = " "

	if (p < 0):
		for s in output:
			if (s):
				s = " "*(-1*p) + s
    
		for s in link_above:
			if (s):
				s = " "*(-1*p) + s

	if level < h - 1:
		p = max(p, len(output[level + 1]))
	if (level > 0):
		p = max(p, len(output[level - 1]))
	p = max(p, len(output[level]))

	# Fill in to left
	if (node.left):
		leftData = SP + str(node.left.data) + SP
		draw_node(output, link_above, node.left, level + 1, p - len(leftData),'L')
		p = max(p, len(output[level + 1]))

	# Enter this data
	space = p - len(output[level])
	if (space > 0):
		output[level] += (' ' * space)
	node_data = SP + str(node.data) + SP
	output[level] += node_data

	# Add vertical link above
	space = p + len(SP) - len(link_above[level])
	if (space > 0):
		link_above[level] += (' ' * space)
	link_above[level] += link_char

	# Fill in to right
	if (node.right):
		draw_node(output, link_above, node.right, level + 1, len(output[level]),'R')
  
def display_tree(root):
	if (root == None):
		print("\tNone")
	h = height(root)
	output = []
	link_above = []
	for i in range(0,h): 
				output.append("")
				link_above.append("")
	draw_node(output, link_above, root, 0, 5, ' ')

	# Create link lines
	for i in range(h):
		for j in range(len(link_above[i])):
			if (link_above[i][j] != ' '):
				size = len(output[i - 1])
				if (size < j + 1):
					output[i - 1] += " " *(j + 1 - size)
				jj = j
				if (link_above[i][j] == 'L'):
					while (output[i - 1][jj] == ' '):
						jj += 1
					for k in range(j+1, jj-1):
						str1 = output[i - 1]
						list1 = list(str1)
						list1[k] = '_'
						output[i - 1] = ''.join(list1)
				elif(link_above[i][j] == 'R'):
					while (output[i - 1][jj] == ' '):
						jj-=1
					
					# k = j-1
					for k in range(j-1,jj+1,-1):
						temp = output[i - 1]
						list1 = list(temp)
						list1[k] = '_'
						output[i - 1] = ''.join(list1)
						k = k - 1
      
				str1 = link_above[i]
				list1 = list(str1)
				list1[j] = '|'
				link_above[i] = ''.join(list1)
					
	# Output
	for i in range(h):
		if (i):
			print("\t" , link_above[i])
		print("\t" , output[i])




from TreeNode import *

def build_tree_helper(p_order, i_order, left, right, mapping, p_index):
    # if left > right, it means there are no more nodes left to construct
    if left > right:
        return None
 
    # Pick current node from preorder list
    # using p_index and increment p_index
    curr = p_order[p_index[0]]
    p_index[0] += 1
    root = TreeNode(curr)
 
    # If this node has no children then return
    if left == right:
        return root
 
    # Else find the index of this
    # node in inorder list
    in_index = mapping[curr]
    
    # Recursively build the left subtree by calling build_tree_helper
    # on the elements in the inorder list from left to in_index - 1
    root.left = build_tree_helper(p_order, i_order, left, in_index - 1, mapping, p_index)

    # Recursively build the right subtree by calling build_tree_helper
    # on the elements in the inorder list from in_index + 1 to right
    root.right = build_tree_helper(p_order, i_order, in_index + 1, right, mapping, p_index)
 
    return root
 
 
def build_tree(p_order, i_order):
    # Explicitly using List object to pass p_index by reference because
    # in python, Pass-by-object-reference is used and simple variable is not an object
    p_index = [0]
    # Using hash map to store the inorder list to reduce time complexity
    # of search to O(1)
    mapping = {}
    
    # Iterate through the inorder list and map each value to its index
    for i in range(len(p_order)):
        mapping[i_order[i]] = i
    
    return build_tree_helper(p_order, i_order, 0, len(p_order) - 1, mapping, p_index)

# Driver code
def main():
    
    p_order = [
        [3, 9, 20, 15, 7],
        [-1],
        [10, 20, 40, 50, 30, 60],
        [1, 2, 4, 5, 3, 6],
        [1, 2, 4, 7, 3],
        [1, 2, 4, 8, 9, 5, 3, 6, 7]
        
    ]
    
    i_order = [
        [9, 3, 15, 20, 7],
        [-1],
        [40, 20, 50, 10, 60, 30],
        [4, 2, 5, 1, 6, 3],
        [4, 2, 7, 1, 3],
        [8, 4, 9, 2, 5, 1, 6, 3, 7]
    ]
    
    indx = 0
    for i in range(len(p_order)):
        
        print(indx+1, ".\tPre order: ", p_order[indx], sep="")
        print("\tIn order: ", i_order[indx], sep="")
        tr = build_tree(p_order[indx], i_order[indx])
        indx += 1
        print("\n\tBinary tree:")
        display_tree(tr)
        print("-"*100)
        

if __name__ == '__main__':
    main()