Construct Binary Tree from Preorder and Inorder Traversal

Problem Link

Construct Binary Tree from Preorder and Inorder Traversal – LeetCode

Problem: 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.

• inorder is the inorder traversal of the same tree.

Construct and return the binary tree.

Examples

Example 1

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

Output: 
    3
   / \
  9  20
     / \
    15  7

Example 2

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

Output: 
 -1

Constraints

• 1 <= preorder.length <= 3000

• inorder.length == preorder.length

• -3000 <= Node.val <= 3000

• All values of preorder and inorder are unique

• inorder is a permutation of preorder

• preorder and inorder represent a valid binary tree

Intuition

The preorder traversal gives the root first, while inorder gives left-subtree → root → right-subtree.

By using the root from preorder and locating it in inorder, we can:

• Partition the inorder array into left and right subtrees.

• Recursively apply this process to build the full tree.

Approach

1. Maintain an index (preIndex) to track the root in the preorder array.

2. Use a hashmap to store the index of each element in the inorder array for O(1) lookups.

3. Recursively:

   • Pick preorder[preIndex] as the root

   • Partition the inorder array based on this root value

   • Recurse on left and right subtrees using the updated ranges

Code (Java)

class Solution {
    private int preIndex = 0;
    private Map<Integer, Integer> inorderIndexMap;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        inorderIndexMap = new HashMap<>();
        for(int i = 0; i < inorder.length; i++) {
            inorderIndexMap.put(inorder[i], i);
        }

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

    private TreeNode build(int[] preorder, int inStart, int inEnd) {
        if (inStart > inEnd) return null;

        int rootVal = preorder[preIndex++];
        TreeNode root = new TreeNode(rootVal);

        int inIndex = inorderIndexMap.get(rootVal);

        root.left = build(preorder, inStart, inIndex - 1);
        root.right = build(preorder, inIndex + 1, inEnd);

        return root;
    }
}

Time and Space Complexity

• Time Complexity: O(N)
  Each node is visited once, and index lookups are done in constant time using a hashmap.

• Space Complexity: O(N)
  Hashmap stores N elements, and recursion stack can go up to O(N) in worst case (skewed tree).

Dry Run

Input:

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

1. preIndex = 0, root = 3 → inorder index = 1

2. Left subtree: inorder[0:0] → [9], preorder[1...]

3. Right subtree: inorder[2:4] → [15, 20, 7], preorder[2...]

Build tree recursively:

• Left of 3 → 9 (leaf)

• Right of 3 → root = 20 → left = 15, right = 7

Conclusion

• This is a classic tree construction problem using preorder and inorder properties.

• Efficient construction requires hashmap for index lookups and careful preorder pointer management.

• Very common in tree-based interview problems.