Construct Binary Tree from Preorder and Inorder — LC 105 O(n) HashMap Interview Guide

Problem Statement#

Given two integer arrays preorder and inorder representing the preorder and inorder traversals of the same binary tree, construct and return the tree.

Constraints:

• 1 less than or equal to preorder length less than or equal to 3000
• inorder length equals preorder length
• All values are unique
• preorder is the preorder traversal of the tree
• inorder is the inorder traversal of the tree

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

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

Why This Problem Matters#

LeetCode 105 Construct Binary Tree from Preorder and Inorder is a Medium problem favored by Amazon, Google, Microsoft, Meta, and Bloomberg. It tests two skills at once: understanding what each traversal encodes and divide-and-conquer recursion with shared state.

The defining insight is that two traversals (preorder + inorder, or postorder + inorder) uniquely determine a binary tree when values are distinct. Preorder gives roots in the order they should be created; inorder splits each subtree into left and right halves. The HashMap-on-inorder optimization is the difference between an O(n) and an O(n^2) solution and is what interviewers actively look for.

This problem also pairs with LC 106 (postorder + inorder), LC 297 (Serialize/Deserialize), and LC 1008 (BST from preorder). Mastering the template here makes those problems mostly mechanical.

The Core Insight#

• Preorder = [root, left subtree, right subtree] — the first element is always the root.
• Inorder = [left subtree, root, right subtree] — the root's index splits left from right.

Recurse with two ideas:

1. Use a shared pre_idx pointer that always reads the next root from preorder.
2. Use bounds (lo, hi) over the inorder array to delimit the current subtree.

At each call:

1. Read root_val = preorder[pre_idx] and increment pre_idx.
2. Find mid = inorder_index[root_val] in O(1) via the precomputed HashMap.
3. Recurse on the left subtree first using bounds (lo, mid - 1).
4. Recurse on the right subtree using bounds (mid + 1, hi).

Building left before right is essential — preorder consumes the entire left subtree's nodes before the right.

Visual Dry Run#

preorder = [3, 9, 20, 15, 7], inorder = [9, 3, 15, 20, 7]. inorder_index = {9: 0, 3: 1, 15: 2, 20: 3, 7: 4}.

Resulting tree: 3 -> {9, 20 -> {15, 7}}.

Solution (Optimal)#

class Solution:
    def buildTree(self, preorder, inorder):
        inorder_index = {val: idx for idx, val in enumerate(inorder)}
        self.pre_idx = 0
 
        def build(lo, hi):
            if lo > hi:
                return None
            root_val = preorder[self.pre_idx]
            self.pre_idx += 1
            root = TreeNode(root_val)
            mid = inorder_index[root_val]
            root.left = build(lo, mid - 1)
            root.right = build(mid + 1, hi)
            return root
 
        return build(0, len(inorder) - 1)

var buildTree = function(preorder, inorder) {
    const inorderIndex = new Map();
    for (let i = 0; i < inorder.length; i++) {
        inorderIndex.set(inorder[i], i);
    }
    let preIdx = 0;
 
    const build = (lo, hi) => {
        if (lo > hi) return null;
        const rootVal = preorder[preIdx++];
        const root = new TreeNode(rootVal);
        const mid = inorderIndex.get(rootVal);
        root.left = build(lo, mid - 1);
        root.right = build(mid + 1, hi);
        return root;
    };
 
    return build(0, inorder.length - 1);
};

Time: O(n) — each node is created once; HashMap lookup is O(1) per call. Space: O(n) — HashMap stores n entries; recursion stack is O(h).

Common Mistakes#

• Slicing preorder[1:] and inorder[:mid] at each call — O(n^2) time and O(n^2) memory due to copies
• Linear-scanning inorder for mid instead of using the HashMap — O(n^2) total time
• Building right subtree before left — wrong, because preorder consumes left first
• Forgetting to increment pre_idx after creating the root, causing infinite recursion
• Off-by-one in bounds — left is (lo, mid - 1), right is (mid + 1, hi), never share mid

Interview Tips#

• Sketch a small tree, write its preorder and inorder, and label what each array slice means
• Explicitly say "left subtree first because preorder is root-left-right"
• Mention the HashMap optimization upfront — it is the senior-level signal
• Note the alternative slicing approach exists but is O(n^2) and only useful for tiny inputs

Follow-up Questions#

• Postorder + Inorder (LC 106) — read root from end of postorder, build right before left
• Preorder + Postorder (LC 889) — solution exists for full binary trees, otherwise ambiguous
• Reconstruct BST from preorder alone (LC 1008) — use BST property, no inorder needed
• Serialize and Deserialize Binary Tree (LC 297) — encode null markers in preorder for unique reconstruction

Key Takeaways#

• LeetCode 105 Construct Binary Tree from Preorder and Inorder is Medium and frequently asked at Amazon, Google, Microsoft, Meta, and Bloomberg
• Time is O(n); space is O(n) for the HashMap plus O(h) recursion stack
• Two traversals (preorder + inorder, or postorder + inorder) uniquely determine a binary tree when values are distinct
• Preorder gives roots in creation order; inorder splits each subtree into left and right halves
• HashMap on inorder values gives O(1) split-point lookup; without it the solution is O(n^2)
• Always build the left subtree before the right because preorder consumes left first
• Same template solves LC 106 (postorder + inorder) and LC 1008 (BST from preorder)