Construct Binary Tree from Preorder and Inorder Traversal

Description

Construct Binary Tree from Preorder and Inorder Traversal

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.

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]

Constraints:

• 1 <= preorder.length <= 3000
• inorder.length == preorder.length
• -3000 <= preorder[i], inorder[i] <= 3000
• preorder and inorder consist of unique values.
• Each value of inorder also appears in preorder.
• preorder is guaranteed to be the preorder traversal of the tree.
• inorder is guaranteed to be the inorder traversal of the tree.

Approach 1: Recursive Divide & Conquer with HashMap ($O(N)$ Time, $O(N)$ Space)

Intuition

1. The first element of preorder is always the root of the tree/subtree.
2. Locating that root element in inorder splits the tree:
   • Everything to the left of the root index in inorder belongs to the left subtree.
   • Everything to the right belongs to the right subtree.
3. We store all inorder value-to-index mappings in a HashMap upfront for $O(1)$ lookups.
4. Recursively build the left subtree first (since preorder processes left children next), then the right subtree.

import java.util.HashMap;
import java.util.Map;
 
class Solution {
    private int preIndex = 0;
    private Map<Integer, Integer> inorderMap;
 
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        inorderMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }
        return build(preorder, 0, inorder.length - 1);
    }
 
    private TreeNode build(int[] preorder, int left, int right) {
        if (left > right) return null;
 
        int rootVal = preorder[preIndex++];
        TreeNode root = new TreeNode(rootVal);
 
        int inorderIndex = inorderMap.get(rootVal);
 
        // Build left subtree first, then right subtree
        root.left = build(preorder, left, inorderIndex - 1);
        root.right = build(preorder, inorderIndex + 1, right);
 
        return root;
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Pre-building the inorderMap takes $O(N)$, and each node is processed exactly once in $O(1)$ time.
• Space Complexity: $O(N)$ — $O(N)$ space for the HashMap plus $O(H)$ recursion stack space ($O(N)$ in worst case for skewed trees).

---

Approach 2: Iterative Stack ($O(N)$ Time, $O(N)$ Space)

Intuition

Simulate the preorder traversal sequence using a stack and an inorderIndex pointer:

1. Push preorder[0] as the root onto the stack.
2. Iterate through preorder starting from index 1:
   • If stack top $\ne$ inorder[inorderIndex]: The next element is a left child of the current node. Attach it to node.left and push it onto the stack.
   • If stack top $=$ inorder[inorderIndex]: We’ve reached the bottom of a left branch. Pop nodes from the stack while they match inorder[inorderIndex]. The next element is the right child of the last popped node. Attach it and push it onto the stack.

import java.util.ArrayDeque;
import java.util.Deque;
 
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0) return null;
 
        TreeNode root = new TreeNode(preorder[0]);
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
 
        int inorderIndex = 0;
 
        for (int i = 1; i < preorder.length; i++) {
            int val = preorder[i];
            TreeNode node = stack.peek();
 
            if (node.val != inorder[inorderIndex]) {
                node.left = new TreeNode(val);
                stack.push(node.left);
            } else {
                while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
                    node = stack.pop();
                    inorderIndex++;
                }
                node.right = new TreeNode(val);
                stack.push(node.right);
            }
        }
 
        return root;
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Each element in preorder is pushed and popped from the stack at most once.
• Space Complexity: $O(N)$ — The stack stores at most $N$ tree nodes.

---

Easy Memory Rule

“preorder[0] is Root $\to$ Find Root in inorder using HashMap $\to$ Left of Root = Left Subtree, Right of Root = Right Subtree!”