[DFS] Construct Binary Tree from Preorder and Inorder Traversal

1. Example

in-order sequence: 4 2 5 (1) 6 7 3 8
pre-order sequence: (1) 2 4 5 3 7 6 8
The constructed tree is

                       1
                   /        \
                  2         3
               /    \       /   \
             4      5    7    8
                          /
                         6

2. Implementation
Q1: inorder ?
A1: root in the middle
Q1: preorder?
A1: root in the first element (arr, left , right), root.left ,and root.right

//NOTE: // validate the input

 if (preorder == null || inorder == null)

 return null;

// Time:O(n), Space:O(n)
public TreeNode buildTree(int[] preorder, int[] inorder)
{

     //NOTE:
     // validate the input
     if (preorder == null || inorder == null)
       return null;

     

     HashMap map = new HashMap();
     for (int i = 0 ; i < inorder.length ; i++)
          map.add(inorder[i], i);




     return buildTree(preorder, 0, preorder.length-1, inorder ,0 , inorder.length -1, map);




}

public TreeNode buildTree(int[] preorder, int preL, int preR, int[] inorder, int inL, int inR, HashMap map)
{
         
        // Base Case, only one element any increment decrement would out of boundary
        if (preL > preR || inL > inR)
           return null;

         
         TreeNode root = new TreeNode(preorder[preL]);
         int index = map.containsKey(root.val);
         root.left = buildTree(preorder,preL+1, preL+(index-inL), inorder, inL, index-1,map);
         root.right = buildTree(preorder,preR-(inR-index-1) ,preR,inorder, index+1, inR, map);

         return root;
}

3. Similar ones
(M) Construct Binary Tree from Inorder and Postorder Traversal