Skip to main content

71. Construct Binary Tree from Preorder and Inorder Traversal

mediumAsked at Vercel

Build a binary tree from its preorder and inorder traversals. Vercel asks this for the recursive split-by-root pattern — same shape as reconstructing a route tree from serialized formats they ingest from third-party config systems.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Vercel loops.

  • Glassdoor (2025-Q4)— Vercel platform onsite; index-based split expected.
  • Blind (2026-Q1)— Listed in Vercel screen pool.

Problem

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Constraints

  • 1 <= preorder.length <= 3000
  • inorder.length == preorder.length
  • -3000 <= preorder[i], inorder[i] <= 3000
  • preorder and inorder consist of unique values.
  • Each value of inorder also appears in preorder.

Examples

Example 1

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

Example 2

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

Approaches

1. Recursion with indexOf

Root is preorder[0]. Find it in inorder; everything left is left subtree, everything right is right.

Time
O(n^2) due to indexOf
Space
O(n)
function buildTree(preorder, inorder) {
  if (!preorder.length) return null;
  const rootVal = preorder[0];
  const idx = inorder.indexOf(rootVal);
  return {
    val: rootVal,
    left: buildTree(preorder.slice(1, idx + 1), inorder.slice(0, idx)),
    right: buildTree(preorder.slice(idx + 1), inorder.slice(idx + 1)),
  };
}

Tradeoff: Quadratic from indexOf and slice. Mention but pivot.

2. Hash map + index-based recursion (optimal)

Precompute value-to-index map for inorder. Recurse with index ranges instead of slicing.

Time
O(n)
Space
O(n)
function buildTree(preorder, inorder) {
  const idxMap = new Map();
  inorder.forEach((v, i) => idxMap.set(v, i));
  let preIdx = 0;
  function build(inLo, inHi) {
    if (inLo > inHi) return null;
    const rootVal = preorder[preIdx++];
    const idx = idxMap.get(rootVal);
    const node = { val: rootVal, left: null, right: null };
    node.left = build(inLo, idx - 1);
    node.right = build(idx + 1, inHi);
    return node;
  }
  return build(0, inorder.length - 1);
}

Tradeoff: O(n) total. The trick: preIdx is a SHARED counter that advances as we consume the preorder. Left must be built before right because preorder visits left first.

Vercel-specific tips

Vercel grades the linear-time version. Bonus signal: emphasizing that the preorder counter MUST be a closure variable (shared across recursive calls) and that left MUST be recursed before right (because preorder dictates that order).

Common mistakes

  • Building right before left — corrupts the preorder counter.
  • Using slice() instead of index ranges — O(n) per slice, O(n^2) total.
  • Forgetting the hash-map precomputation — indexOf inside recursion.

Follow-up questions

An interviewer at Vercel may pivot to one of these next:

  • Construct from inorder + postorder (LC 106).
  • Construct from preorder + postorder (LC 889) — not always unique.
  • Why don't preorder + level-order suffice on their own?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why must left be built first?

Preorder is root, left, right. After consuming the root, the next preorder element is the root of the left subtree. So we must consume left before right.

Why does this need TWO traversals?

Preorder alone doesn't tell you where the left subtree ends. Inorder gives that boundary because the root splits inorder into left and right subtrees.

Practice these live with InterviewChamp.AI

Drill Construct Binary Tree from Preorder and Inorder Traversal and other Vercel interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →