Skip to main content

72. Construct Binary Tree from Preorder and Inorder Traversal

mediumAsked at Plaid

Reconstruct a binary tree from its preorder and inorder traversals. Plaid asks this because deserializing a tree from two stream snapshots (preorder = parent-first, inorder = sorted) is the same reconstruction primitive.

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

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • Glassdoor (2025)— Plaid SWE III onsite — tree-reconstruction classic.
  • LeetCode Discuss (2026)— Plaid construction problem.

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.

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. Recursive with linear search

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

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

Tradeoff: Clear but indexOf and slice make it quadratic.

2. Recursive with inorder index map

Pre-build a value-to-index map for inorder. Use indices instead of slicing.

Time
O(n)
Space
O(n)
function buildTree(preorder, inorder) {
  const idx = new Map();
  inorder.forEach((v, i) => idx.set(v, i));
  let p = 0;
  function go(lo, hi) {
    if (lo > hi) return null;
    const v = preorder[p++];
    const m = idx.get(v);
    const node = { val: v, left: null, right: null };
    node.left = go(lo, m - 1);
    node.right = go(m + 1, hi);
    return node;
  }
  return go(0, inorder.length - 1);
}

Tradeoff: Linear time. The index map collapses the O(n) lookup to O(1); using lo/hi indices avoids the O(n) slice.

Plaid-specific tips

Plaid grades this on whether you spot the O(n^2) trap. Bonus signal: explain why preorder gives root and inorder gives left/right partition. Connect to deserializing a category tree from two stream snapshots (top-down vs sorted) in their analytics pipeline.

Common mistakes

  • Using slice() and indexOf in the recursive case — quadratic.
  • Off-by-one on inorder index bounds (m - 1 vs m).
  • Forgetting that preorder shrinks as we consume the global pointer p.

Follow-up questions

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

  • From postorder and inorder (LC 106).
  • From preorder and postorder (LC 889).
  • Serialize and deserialize a tree (LC 297).

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 does this need both traversals?

Preorder alone doesn't pin tree shape (siblings vs children are ambiguous). Inorder gives the left/right split for any given root.

Why is the global p pointer needed?

Each recursive call consumes the next preorder value. A global pointer is simpler than computing the offset for each subtree.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →