Construct Binary Tree from Preorder and Inorder Traversal

Examples

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

Preorder always starts with the root, so 3 is the root. In inorder, everything left of 3 (just [9]) is the left subtree, and everything right of it ([15,20,7]) is the right subtree.

Input: preorder = [-1], inorder = [-1]
Output: [-1]

A single-node tree.

Constraints

• 1 <= preorder.length <= 3000

• inorder.length == preorder.length

• All values in preorder and inorder are unique, and every value in inorder also appears in preorder.

Approach

Preorder's first element is always the current subtree's root. Once you know the root's value, look it up in the inorder array: everything to its left in that array is the entire left subtree (in inorder order), and everything to its right is the entire right subtree. Recursing on those two pieces rebuilds the tree.

The direct version of this re-searches the inorder array and copies sub-arrays on every call, which adds up. The optimized version precomputes where every value sits in inorder, and tracks subtree boundaries with plain indices instead of copying arrays.

Solutions

Brute Force — Search and Slice

At each recursive call, take the first element of the current preorder slice as the root, use indexOf to find that value's position in the current inorder slice, and slice both arrays into "left part" and "right part" for the recursive calls. Simple to follow, but repeatedly searching and copying arrays adds real overhead.

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function buildTree(preorder, inorder) {
  if (preorder.length === 0) return null;

  const rootVal = preorder[0];
  const root = new TreeNode(rootVal);

  const mid = inorder.indexOf(rootVal);
  root.left = buildTree(preorder.slice(1, mid + 1), inorder.slice(0, mid));
  root.right = buildTree(preorder.slice(mid + 1), inorder.slice(mid + 1));

  return root;
}

Time: O(n^2) — indexOf and slice each cost O(n), across O(n) calls · Space: O(n^2) — repeated array copies from slicing

Optimal — Index Map with Boundary Pointers

First, build a map from value to its index in inorder, so finding the root's split point is instant instead of a linear search. Then, instead of slicing arrays, track the current subtree using just a range of indices into inorder, and a single shared pointer into preorder that always points at the next root to place (preorder never needs to be re-sliced, since its values are consumed strictly in order as you recurse).

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function buildTree(preorder, inorder) {
  const indexOfInorder = new Map();
  inorder.forEach((val, idx) => indexOfInorder.set(val, idx));

  let preorderIndex = 0;

  function build(inorderLeft, inorderRight) {
    if (inorderLeft > inorderRight) return null;

    const rootVal = preorder[preorderIndex];
    preorderIndex++;

    const root = new TreeNode(rootVal);
    const mid = indexOfInorder.get(rootVal);

    root.left = build(inorderLeft, mid - 1);
    root.right = build(mid + 1, inorderRight);
    return root;
  }

  return build(0, inorder.length - 1);
}

Time: O(n) · Space: O(n) — the index map, plus O(h) recursion stack