Construct Binary Tree from Preorder & Inorder

Difficulty: Hard

Problem

Given two integer arrays — the preorder and inorder traversals of the same binary tree (all values distinct) — rebuild the original tree and return its root. You mastered producing these traversals; now you'll run them in reverse.

Example

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
Explanation: Preorder's first value (3) must be the root. In inorder, everything before 3 ([9]) is its left subtree and everything after ([15,20,7]) is its right. Repeat inside each part and the whole tree reappears.

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

  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