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 = [40,25,60,10,55,30], inorder = [60,25,10,40,55,30]
Output: [40,25,55,60,10,null,30]
Explanation: The first preorder value, 40, is the root. In the inorder list, [60,25,10] lies left of 40 and [55,30] lies right of it. Repeat on each side: the left part's preorder starts with 25, which splits into 60 and 10; the right part's starts with 55, which has no left side and 30 on its right. Note that inorder is not sorted here: the values can come in any order, so the tree is found by position, never by comparing values.

Brute-force approach

The first idea, counted: sort every other preorder value by looking it up in inorder's left side, and scan inorder to find each root. That is 18 looks on the six-node example and exactly 1,000,000 on a left-leaning chain of 1,000 nodes. The slicing version (500,500 scans and 999,000 copies on that chain) is the middle step; the lesson builds the windowed O(n) version.

Steps

  1. Take preorder[0] as the root and scan inorder for it
  2. Look up every other preorder value in inorder's left side to sort it into left or right
  3. Repeat inside each side
  4. Count: 18 looks on the example, 1,000,000 on a chain of 1,000

Time complexity: O(n^2) · Space complexity: O(h) recursion

Trade-offs

  • Every call re-scans inorder for its root and re-sorts its values: 1,000,000 looks on a chain of 1,000
  • Slicing the arrays on top of that copies another 999,000 values
  • A dictionary of inorder positions plus (lo, hi) windows removes both costs

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

  1. Build a value → index map of inorder
  2. Keep a pointer pre_i starting at 0, the next root to use
  3. build(lo, hi): if the window is empty, return null
  4. Take preorder[pre_i] as the root, advance pre_i, find its inorder position mid
  5. 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).

Related problems

Keep practising