Construct Binary Tree From Preorder And Inorder Traversal

MEDIUM✓ CHIP-TIMEDLC #105 — FULL STATEMENT ↗

The drill: Two traversal orders, one unique tree — rebuild the exact original shape from a preorder list and an inorder list of the same distinct values.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

Two lists arrive describing the same binary tree from different angles — one in preorder, one in inorder — and the job is rebuilding the one tree that produces both.

Every value in the tree is distinct, which is what makes the reconstruction unambiguous: there's exactly one tree shape consistent with both traversals at once.

The output is the root of that rebuilt tree, matching the original in every branch, every leaf, and every null gap.

EX 01

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

→ [3, 9, 20, null, null, 15, 7]

CLASSIC UNBALANCED SHAPE

EX 02

preorder = [1] · inorder = [1]

→ [1]

SINGLE NODE

EX 03

preorder = [] · inorder = []

→ []

EMPTY

both lists have equal length and describe the same node set
values are unique across the whole tree — no duplicates to disambiguate
tree sizes stay in the low thousands of nodes
exactly one valid tree reconstructs from the pair

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Preorder always names the current subtree's root first. Inorder splits everything left of that root's position into the left subtree and everything right of it into the right subtree.

HINT 2 THE STRUCTURE

Once you know the root and where it sits in inorder, the sizes of the left and right pieces fall out immediately — same trick applies recursively to every subtree.

HINT 3 ONE STEP FROM THE ANSWER

Recurse with an index into preorder (advancing by one each call) and a (left, right) window into inorder. A hashmap from value to inorder index turns "where does the root sit" into an O(1) lookup instead of a scan.

COACH'S BOARD — THE PATTERN, STEP BY STEP

TWO LISTS, ONE TREEPATTERN · HASHMAP + INDEX WINDOWpreorder = [3, 9, 20, 15, 7] · inorder = [9, 3, 15, 20, 7]

STEP 1

Preorder always names a subtree's root first: 3, 9, 20, 15, 7. Inorder tells us where each root splits left from right.

STEP 1 / 7 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/construct-binary-tree-from-preorder-and-inorder-traversal.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        index = {v: i for i, v in enumerate(inorder)}
        pos = [0]

        def helper(lo: int, hi: int) -> Optional[TreeNode]:
            if lo > hi:
                return None
            root_val = preorder[pos[0]]
            pos[0] += 1
            root = TreeNode(root_val)
            mid = index[root_val]
            root.left = helper(lo, mid - 1)
            root.right = helper(mid + 1, hi)
            return root

        return helper(0, len(inorder) - 1)

TIME O(N)SPACE O(N)PYTHON · RACE PACE · 17 LN

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if not preorder:
            return None
        root_val = preorder[0]
        root = TreeNode(root_val)
        mid = inorder.index(root_val)          # linear scan, every call
        root.left = self.buildTree(preorder[1:mid + 1], inorder[:mid])
        root.right = self.buildTree(preorder[mid + 1:], inorder[mid + 1:])
        return root

TIME O(N²)SPACE O(N²)PYTHON · TRAINING PACE · 10 LN

class Solution {
    private int[] preorder;
    private int pos;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.pos = 0;
        Map<Integer, Integer> index = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            index.put(inorder[i], i);
        }
        return helper(0, inorder.length - 1, index);
    }

    private TreeNode helper(int lo, int hi, Map<Integer, Integer> index) {
        if (lo > hi) {
            return null;
        }
        int rootVal = preorder[pos++];
        TreeNode root = new TreeNode(rootVal);
        int mid = index.get(rootVal);
        root.left = helper(lo, mid - 1, index);
        root.right = helper(mid + 1, hi, index);
        return root;
    }
}

TIME O(N)SPACE O(N)JAVA · RACE PACE · 26 LN

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0) {
            return null;
        }
        int rootVal = preorder[0];
        TreeNode root = new TreeNode(rootVal);
        int mid = indexOf(inorder, rootVal);
        root.left = buildTree(Arrays.copyOfRange(preorder, 1, mid + 1), Arrays.copyOfRange(inorder, 0, mid));
        root.right = buildTree(Arrays.copyOfRange(preorder, mid + 1, preorder.length), Arrays.copyOfRange(inorder, mid + 1, inorder.length));
        return root;
    }

    private int indexOf(int[] arr, int val) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == val) {
                return i;
            }
        }
        return -1;
    }
}

TIME O(N²)SPACE O(N²)JAVA · TRAINING PACE · 22 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED