Construct Binary Tree from Preorder & Inorder

Difficulty: Hard

Problem

Two integer arrays describe the same binary tree with all-distinct values: one is its preorder walk and the other is its inorder walk. Reconstruct the tree and return its root. Having practised producing these walks, now reverse the process.

Example

Input: preorder = [8,4,2,6,12], inorder = [2,4,6,8,12]
Output: [8,4,12,2,6]
Explanation: The first preorder value, 8, is the root. In the inorder list, [2,4,6] lies left of 8 and [12] lies right of it. Repeat on each side: the left part's preorder starts with 4, which splits into 2 and 6.

Brute-force approach

The readable-but-slow variant slices new arrays at every step (O(n²) time and memory). The lesson builds the windowed O(n) version directly, same idea, no waste.

Optimal approach

Key insight: Preorder tells you WHO each root is; inorder tells you WHAT belongs on each side of it. Together they pin down exactly one tree.

Consume roots from preorder left to right; for each root, find its position in inorder (via a prebuilt map) to know how many values belong to its left and right subtrees; recurse on those windows.

Steps

Build a value → index map of inorder
Keep a pointer pre_i starting at 0, the next root to use
build(lo, hi): if the window is empty, return null
Take preorder[pre_i] as the root, advance pre_i, find its inorder position mid
root.left = build(lo, mid−1), then root.right = build(mid+1, hi)

Time complexity: O(n) · Space complexity: O(n) for the index map + O(h) recursion

Pseudocode

function buildTree(preorder, inorder):
    idx = map from value -> inorder index
    pre_i = 0
    
    function build(lo, hi):
        if lo > hi:
            return ____
        
        val = preorder[____]
        pre_i = pre_i + 1
        root = new TreeNode(val)
        mid = ____[val]
        
        root.left  = build(lo, ____)
        root.right = build(____, hi)
        return root
    
    return build(0, length(inorder) - 1)

Hints

An empty window means there is no subtree here, what do we return?
The next root always comes from preorder at the marching pointer
Where do we look up the root's position in inorder instantly?
The left window ends just BEFORE mid; the right window starts just AFTER it

Complexity questions

What is the time complexity using the index map?

O(n): each of the n nodes is built once with an O(1) lookup. Building the map is O(n). Then every node costs O(1): one pointer advance, one map lookup, two recursive dispatches. Total O(n).

What happens if we scan inorder to locate each root instead?

O(n²) worst case: an O(n) scan for each of n nodes, painful on skewed trees. Each scan is O(window size). On a skewed tree the windows shrink by only one element per level, so the scans sum to 1+2+...+n = O(n²).

What is the space complexity of the windowed solution?

O(n) for the map plus O(h) recursion, and no subarray copies thanks to the windows. The map stores n entries; the recursion stack reaches the tree's height. Slicing-based versions ALSO pay O(n²) for subarray copies: the (lo, hi) windows eliminate that entirely.

Could postorder + inorder rebuild the tree too?

Yes: postorder's LAST element is the root; consume from the END and build right-before-left. Postorder is Left → Right → Root, so roots come from the back. Mirror everything: consume from the end, recurse right window first. (Preorder + postorder alone, though, stays ambiguous for single-child nodes.)

Check your understanding of Construct Binary Tree from Preorder & Inorder

What does preorder hand us on a silver platter?

The ROOT: it's always the FIRST element, and as we recurse, preorder keeps yielding each subtree's root in exactly the right order. Preorder is Root → Left → Right, so position 0 is the whole tree's root. Even better: because roots always come before their subtrees, reading preorder left-to-right supplies every subtree's root exactly when the rebuild needs it.

Once we know the root, what does inorder tell us?

WHERE to split: values before the root's position form the left subtree, values after it form the right. Inorder is Left → Root → Right. So in the inorder array, the root sits exactly between its left subtree's values and its right subtree's values, finding it physically splits the array in two.

preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]. The root is 3. What exactly is in its LEFT subtree?

[9]: the values before 3 in inorder. In inorder, only 9 appears before 3, so the left subtree contains exactly one node: 9. The remaining [15,20,7] all sit after 3, forming the right subtree.

Why can't ONE traversal alone (say just preorder) determine the tree?

Different tree shapes can share the same preorder, e.g. [1,2] as a left-only chain and as a right-only chain both give preorder [1,2]. Root 1 with left child 2, and root 1 with right child 2, BOTH produce preorder [1,2]. But their inorders differ ([2,1] vs [1,2]). The second traversal is what disambiguates the shape.

Why do we build a value → index map for inorder before starting?

Scanning inorder to locate each root costs O(n) per node → O(n²) total; the map makes each lookup O(1) → O(n) total. Every one of the n rebuilt nodes needs its position in inorder. A linear scan each time gives O(n²) on skewed inputs; a one-time hash map turns every lookup into O(1).