#134

Construct Binary Tree from Preorder and Inorder Traversal

medium

arrayhash-tabledivide-and-conquertreebinary-tree

Given two integer arrays preorder and inorder — the preorder and inorder traversals of the same binary tree, with all values distinct — reconstruct and return the tree.

In preorder, the first element is always the root. In inorder, everything left of the root belongs to the left subtree and everything right of it to the right subtree. Recurse on each side.

The reconstructed tree is returned as a level-order array where null marks a missing child.

Example

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

Output: [3,9,20,null,null,15,7]9315207

3 is the root; 9 is left of it inorder (left subtree), 15/20/7 are right.

Constraints

1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder and inorder consist of unique values; inorder is a permutation of preorder.

Intuition

Two facts drive the reconstruction. In preorder (node, left, right) the very first value is the root. In inorder (left, node, right) the root splits the array: everything to its left is the left subtree, everything to its right is the right subtree. Recurse on each side. A direct version searches inorder for the root each time and slices fresh arrays for the recursion.

function buildTree(preorder, inorder) {
  if (preorder.length === 0) return null;
  const rootVal = preorder[0];          // preorder's first value is the root
  const mid = inorder.indexOf(rootVal); // O(n) search splits inorder
  const node = new TreeNode(rootVal);
  // Left subtree: the first `mid` preorder values after the root, and inorder[0..mid).
  node.left = buildTree(preorder.slice(1, mid + 1), inorder.slice(0, mid));
  // Right subtree: the rest.
  node.right = buildTree(preorder.slice(mid + 1), inorder.slice(mid + 1));
  return node;
}

Brute force — linear search for the root + array slicing at every node: O(n²) time and space.

Correct, but two things make it O(n²): the indexOf search at every node, and the slice calls that copy subarrays. Can we do better?

Two optimizations: (1) precompute a value → inorder-index map so the split is O(1) instead of a linear search; (2) stop slicing — instead, pass the inorder range [lo, hi] and consume preorder left-to-right with a single shared cursor. Because preorder is root, then all of the left subtree, then all of the right, advancing the cursor as we recurse left-first hands each subtree its own root automatically.

Tracing preorder = [3, 9, 20, 15, 7], inorder = [9, 3, 15, 20, 7]:

Cursor at `3` (root). In inorder, 3 is at index 1 → left subtree is inorder [9], right is [15, 20, 7].
Recurse left, cursor advances to `9`. Inorder range is just [9] → a leaf. Left and right ranges are empty.
Recurse right, cursor advances to `20`. In inorder, 20 sits between 15 (left) and 7 (right).
Cursor `15` then `7` fill 20's two leaves. The cursor has walked preorder exactly once.

The rebuilt tree is [3, 9, 20, null, null, 15, 7].

The stored solution's mid is the root's index in inorder (from the precomputed map); pre is the shared preorder cursor — there's no lane because the reconstruction is a recursive split, not a scan.
Left-first recursion is essential: it consumes the preorder cursor in the same order the values appear, so each recursive call's first preorder value is its subtree's root.

Optimization

Recursive split with an inorder index map

Take the next preorder value as the current root. Find that value in the inorder array: everything to its left is the left subtree, everything to its right is the right subtree. Recurse, consuming preorder values left subtree first (preorder is root, then all of left, then all of right).

A naive linear search for the root inside inorder makes it O(n²); precompute a value→index map of inorder so the split is O(1).

O(n) time, O(n) space for the map and recursion.

function buildTree(preorder, inorder) {
  // value -> its index in inorder, so the left/right split is O(1).
  const indexOf = new Map();
  inorder.forEach((v, i) => indexOf.set(v, i));
  let pre = 0; // next root to consume from preorder
  // Build the subtree whose inorder slice is [lo, hi].
  const build = (lo, hi) => {
    if (lo > hi) return null;
    const rootVal = preorder[pre++];
    const node = new TreeNode(rootVal);
    const mid = indexOf.get(rootVal); // split point in inorder
    node.left = build(lo, mid - 1);   // left subtree first (matches preorder order)
    node.right = build(mid + 1, hi);
    return node;
  };
  return build(0, inorder.length - 1);
}

Complexity analysis

Time complexity: O(n). Here's why:

Building the value→inorder-index map is one pass — O(n).
The recursion creates each of the n nodes once, finding its split point via the map in O(1).

So O(n), versus the brute force's O(n²) from repeated indexOf searches and array slicing.

Space complexity: O(n). Here's why:

The index map holds n entries.
The recursion stack is O(h), at most O(n) for a skewed tree.

So O(n). The output tree reuses freshly built nodes — the unavoidable result.

Test cases

Beyond the example above, these are worth thinking through before you submit.

Input	Expected output	Description
preorder = [9], inorder = [9]	[9]9	Single node.
preorder = [7,8,9], inorder = [7,8,9]	[7,null,8,null,9]789	Preorder == inorder → a pure right spine.
preorder = [9,8,7], inorder = [7,8,9]	[9,8,null,7]789	Preorder reversed of inorder → a pure left spine.
preorder = [10,20,40,50,30,60,70], inorder = [40,20,50,10,60,30,70]	[10,20,30,40,50,60,70]40205010603070	A perfect tree reconstructed from its two traversals.
preorder = [8,4,2,6], inorder = [2,4,6,8]	[8,4,null,2,6]2468	A left-leaning shape: 4 has two children, 8 only a left subtree.

Try it yourself

Write your solution against the real judge before checking the reference.

Open in editor