Construct Binary Tree from Preorder and Inorder Traversal

Given two integer arrays preorder and inorder — the preorder and inorder traversals of the same binary tree, where all values are unique — construct and return the binary tree.

The tree is returned in level-order (breadth-first), using null for missing children.

Hints

· Stuck? Reveal one nudge at a time.

The first preorder value is the root of the (sub)tree.

Find the root in inorder: values before it are the left subtree, after it the right.

Hash each value to its inorder index for O(1) splits, and walk preorder with one moving pointer.

Common doubts

So the root has exactly one position in inorder; duplicates would make the left/right split ambiguous.

It turns the per-node O(n) search for the root's inorder position into an O(1) lookup, dropping total time from O(n^2) to O(n).

Root first, then the entire left subtree, then the right — exactly preorder, so a single incrementing index suffices.

Interview follow-ups

· What an interviewer asks next.

The root is postorder's LAST element; walk postorder from the back, building the right subtree before the left.

They don't determine where a single child attaches (left vs right), so the tree isn't unique in general.

Fun facts

The same map+pointer technique builds from inorder+postorder by consuming postorder in reverse.
This is the inverse of the traversals you learned first — construction is just traversal run backwards.

Asked at

AmazonMicrosoftBloomberg

Frequently Sometimes Occasionally

Example 1

Input: preorder = [3, 9, 20, 15, 7], inorder = [9, 3, 15, 20, 7]
Output: [3, 9, 20, null, null, 15, 7]
Root 3, left subtree {9}, right subtree rooted at 20 with children 15 and 7.

Example 2

Input: preorder = [-1], inorder = [-1]
Output: [-1]
A single node.

Constraints

- 1 <= preorder.length <= 3000 - inorder.length == preorder.length - -3000 <= values <= 3000 - All values are unique - preorder and inorder are traversals of the same tree

Preorder's first element is the root. Find that root in inorder: everything to its left is the left subtree, everything to its right is the right subtree — and the counts tell you how to split preorder too. Recurse. Searching inorder each time is O(n²); a value→index hash map makes each split O(1), giving O(n).

Prerequisites

Before you start

· Concepts used directly in the solution.

Preorder & inorder. Preorder = node,left,right; inorder = left,node,right.

Root + split. Preorder gives the root; inorder gives the left/right partition.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Inputs

“Are values unique?”

Yes — so a value maps to exactly one inorder position.

“Can the tree be empty?”

Yes — both arrays empty means a null tree.

The ideal opening — say it like this

The first preorder value is the root; I find it in inorder to split into left and right subtrees.

I hash each value to its inorder index so the split is O(1), and consume preorder left-to-right as I recurse.

Understand the problem

Worked example — preorder = [3, 9, 20, 15, 7], inorder = [9, 3, 15, 20, 7]

root = 3 (preorder[0]); in inorder, 3 is at index 1
  left  inorder = [9]        -> subtree {9}
  right inorder = [15,20,7]  -> root 20, split into 15 | 7
result:
        3
       / \
      9   20
         /  \
        15   7

Key observations

1Aha

Preorder gives the root, inorder gives the split

The first preorder value is always the current subtree's root; inorder partitions the rest.

2Aha

A value→index map removes the search

Precomputing inorder indices turns each O(n) search into O(1).

3Aha

One moving preorder pointer

Consuming preorder left-to-right (root, then whole left subtree, then right) needs just an incrementing index.

Brute force vs optimal

	Slice + search inorder	Hash map + index pointer
Idea	Find root in inorder each call, slice arrays	O(1) split via a value->index map
Time	O(n^2)	O(n)
Space	O(n^2) slices	O(n)

Both build the same tree; the map version avoids repeated searching and array copies. Full code is in the Approaches selector below.

Summary

Key takeaway

Root = preorder[0]; split inorder around it into left/right; recurse. Use a value→inorder-index map + a moving preorder pointer for O(n).

build(lo, hi):        # inorder range
    if lo > hi: return null
    root = preorder[pre++]; m = index[root]
    node.left  = build(lo, m-1)
    node.right = build(m+1, hi)