#  105. Construct Binary Tree from Preorder and Inorder Traversal
#  Leetcode solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        def array_to_tree(left,right):
            nonlocal preorder_index
            # if there are no elements to contruct the tree we return none
            if left>right:return None
            
            #select the preorder_index element as root and increment it
            root_value=preorder[preorder_index]
            root=TreeNode(root_value)
            
            preorder_index+=1
            
            #build left and right subtree
            #exclude inorder_index_map[root_value] because it is the root
            
            root.left=array_to_tree(left,inorder_index_map[root_value]-1)
            root.right=array_to_tree(inorder_index_map[root_value]+1,right)
            
            return root
        preorder_index=0
        
        #build haashmap for inorder for contant time lookups
        inorder_index_map={}
        for index,value in enumerate(inorder):
            inorder_index_map[value]=index
        
        return array_to_tree(0,len(preorder)-1)
