Problem 16.11 · Binary TreesMedium

Construct Binary Tree from Preorder and Inorder

PatternTree DFS Divide and Conquer Hash Map Lookup (Complement)

What it teaches: Divide and conquer on traversals: the root splits the in-order list, and a hash map makes it O(n).

Practise it on judges as “Construct Binary Tree from Preorder and Inorder Traversal”.

The problem

Given the pre-order and in-order traversals of a tree with distinct values, rebuild the tree.

Example 1

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

Constraints

1 ≤ n ≤ 3000
Distinct values

Pattern clues in the wording

→ Rebuild structure from two orders

These clues point to Tree DFS: Recurse into the left and right children and combine what they return (height, sums, paths).

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return null;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	preorder = [3,9,20,15,7] inorder = [9,3,15,20,7]	[3,9,20,null,null,15,7]
2	preorder = [-1] inorder = [-1]	[-1]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Recursive split with an index map · O(n)

Recursive split with an index map

Time O(n) Space O(n)

Keep a pointer into preorder. build(lo, hi) over an inorder range: take the next preorder value as root, find its inorder index m, build left from (lo, m − 1) then right from (m + 1, hi).

Approach 1

import java.util.HashMap;
import java.util.Map;

class Solution {
    private int pre = 0;
    private final Map<Integer, Integer> index = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) index.put(inorder[i], i);
        return build(preorder, 0, inorder.length - 1);
    }

    private TreeNode build(int[] preorder, int lo, int hi) {
        if (lo > hi) return null;
        TreeNode root = new TreeNode(preorder[pre++]);
        int m = index.get(root.val);
        root.left = build(preorder, lo, m - 1);     // left must be built first: preorder lists it next
        root.right = build(preorder, m + 1, hi);
        return root;
    }
}

Verdict: Each node is created once with an O(1) lookup.

Before you submit

Edge cases and common mistakes

Test these inputs

Single node
Skewed trees

Mistakes people make

Building the right subtree before the left (the preorder pointer goes out of sync).

Interview

Follow-up questions

Can pre-order and post-order rebuild a tree?

Command Palette

The problem

Approaches

Recursive split with an index map

Edge cases and common mistakes

Follow-up questions