Construct Binary Tree from Preorder and Inorder Traversal

Problem Statement

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree. (link)

Example 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

Example 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]

Solution

Building a Unique Binary Tree: We can only build a unique binary tree if we have two traversals, and one of them must be an inorder traversal. We cannot build a unique binary tree if one is preorder and the other is postorder.

Idea: At any given time, the preorder traversal gives us the current root of the binary tree.

Once we know the root of the tree, we need to find the left and right subarrays in both arrays:

• Inorder array

• Preorder array

Inorder arrays: Finding the left and right subarrays in the inorder array is straightforward once we find the index of the parent element in the inorder array.

Preorder arrays: If you have found the size of the left subarray in the inorder array, use the same size to find the left preorder subarray in the main preorder array. The remaining elements form the right preorder subarray.

inorder = [9,3,15,20,7]
preorder = [3,9,20,15,7], 

Root is 3

Left Inorder - [9]
Left Preorder - [9]

Right Inorder - [15,20,7]
right preorder - [20,15,7]

------
Inorder - [15,20,7]
preorder - [20,15,7]

root 20

Left Inorder - [15]
Left Preorder - [15]

Right Inorder - [7]
right preorder - [7]

Time - O(n)

Space - O(n)

class Solution {

    private TreeNode buildTree(int[] preorder, int preStart, int preEnd,
                               int[] inorder, int inStart, int inEnd, 
                               Map<Integer, Integer> inOrderIndexMap){

        if(preStart>preEnd || inStart>inEnd){
            return null;
        }

        TreeNode root = new TreeNode(preorder[preStart]);

        int parentIndex = inOrderIndexMap.get(root.val);
        int leftSize = parentIndex - inStart;

        root.left = buildTree(preorder, preStart+1, preStart+leftSize,
                        inorder, inStart, parentIndex-1,
                        inOrderIndexMap);

        root.right = buildTree(preorder, preStart+leftSize+1, preEnd,
                        inorder, parentIndex+1, inEnd,
                        inOrderIndexMap);

        return root;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {

        Map<Integer, Integer> inOrderIndexMap = new HashMap<>();

        for(int i=0; i<inorder.length; i++){
            inOrderIndexMap.put(inorder[i], i);
        }

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