[Java] Reconstruct binary tree from visits

An alternative way to represent a binary tree is to use an array. If the tree is a binary search tree and is also perfectly balanced, it's easy to find each node with the formula:

node         = idx of node in array
left child   = 2 * idx of node in array + 1
right child = 2 * idx of node in array + 2

But if the tree is not balanced, we need more information. For example, given a inorder and a postorder visit of the tree, we can rebuild it easily.

The idea is as such:

• in the preorder visit array at position 0 we have the root
• in the inorder visit array before the index of the root found at previous step, we have the left subtree and after we have the right subtree
• we can determine a range to search for our elements inside and recursively compute the left and right subtrees for each subroot

CAUTION: if we have duplicate values this method does not work because we search for unique integer items in both arrays. However, if we get an array of BST (nodes) as input instead, then it will work because each node is always equal to itself as object, without considering the content.

So after getting the root as preorder[0], for the left subtree we should search for the root immediately adjacent the current one in the preorder visit (root_idx + 1) then we should search for the rest of the subtree in the portion between our start and the current subroot (start to subroot_idx) in the inorder visit.

For the right subtree we should search for the root immediately adjacent the last left subtree element we checked in the preorder visit (root_idx + 1 + subroot_idx - start) then we should search for the rest of the subtree in the portion between our current subroot and the our end (subroot_idx + 1 to end) in the inorder visit.

You can check the full code on my Gist (buildTreeFromVisit):

 /*  
   We can build a Binary Tree from its preorder and inorder visits as such:  
   - in the preorder at position 0 we have the root  
   - in the inorder before the index of the root found at previous step, we have the left subtree and after we have the right subtree  
   - we can determine a range to search for our elements inside and recursively compute the left and right subtrees for each subroot  
   
   CAUTION: if we have duplicate values this method does not work because we search for unique integer items in both arrays  
   However, if we get an array of BST (nodes) as input instead, then it will work because each node is always equal to itself as object  
   */  
   private static BST doBuild(int[] preorder, int[] inorder, int start, int end, int root_idx, HashMap<Integer, Integer> in_map){  
     if(end <= start) return null; //this is the child of a leaf  
   
     BST t = new BST(preorder[root_idx]); //add ourselves as root  
   
     //find this root in the inorder visit  
     int subroot_idx = in_map.get(preorder[root_idx]);  
   
     /*  
     the left subtree should search for the root immediately adjacent the current one in the preorder visit (root_idx + 1)  
     it should search for the rest of the subtree in the portion between our start and the current subroot (start to subroot_idx) in the inorder visit  
     */  
     t.setLeft(doBuild(preorder, inorder, start, subroot_idx, root_idx + 1, in_map));  
   
     /*  
     the right subtree should search for the root immediately adjacent the last left subtree element we checked in the preorder visit (root_idx + 1 + subroot_idx - start)  
     it should search for the rest of the subtree in the portion between our current subroot and the our end (subroot_idx + 1 to end) in the inorder visit  
     */  
     t.setRight(doBuild(preorder, inorder, subroot_idx + 1, end, root_idx + 1 + subroot_idx - start, in_map));  
   
     return t;  
   }  
   
   public static BST buildTreeFromVisit(int[] preorder, int[] inorder){  
     if(preorder == null || inorder == null || preorder.length != inorder.length) return null;  
   
     /*  
     with this we bring time down from O(N^2) to O(N) and are still in O(N) space  
     Map from value to index in array  
     */  
     HashMap<Integer, Integer> in_map = new HashMap<>();  
   
     for(int i = 0; i < inorder.length; i++){  
       in_map.put(inorder[i], i);  
     }  
   
     BST out = doBuild(preorder, inorder, 0, preorder.length, 0, in_map);  
   
     return out;  
   }