Skip to main content

76. Construct Binary Tree from Preorder and Inorder Traversal

mediumAsked at Snowflake

Rebuild a binary tree from preorder + inorder traversals. Snowflake asks this to test recursive structure recovery and to set up a discussion on plan-tree deserialization.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2025-Q4)— Snowflake compiler-team uses this for plan-deserialization warm-up.
  • LeetCode Discuss (2025-10)— Reported at Snowflake SDE-I screens.

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

Root = preorder[0]. Find its index in inorder. Recurse left/right on the surrounding subranges.

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

Tradeoff: Slicing makes it O(n^2). Works for n <= 3000 but not elegant.

2. Hash map + index pointers (optimal)

Build a hash map from value to inorder index. Recurse with preIdx (global pointer) and inorder bounds.

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

Tradeoff: Linear, no slicing. The hash map avoids the indexOf scan; the global preIdx avoids passing preorder bounds.

Snowflake-specific tips

Snowflake interviewers want the hash-map + global preIdx optimization. Bonus signal: connect to plan-tree deserialization — when their distributed scheduler ships a compiled plan as serialized bytes, the receiving node reconstructs the tree from a flat traversal using a similar recursive scheme.

Common mistakes

  • Slicing arrays in the recursive call — quadratic complexity.
  • Linear search for the root in inorder — also quadratic.
  • Forgetting that preIdx must be global (or wrapped in a holder), not passed by value.

Follow-up questions

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

  • Construct from inorder and postorder (LC 106).
  • Construct from preorder and postorder (LC 889) — not always unique.
  • How does Snowflake deserialize a query plan?

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 is preIdx global?

Each recursive call consumes the next preorder element. If preIdx were passed by value, the right subtree would lose track of where the left subtree left off.

Why is the hash map necessary?

Without it, finding root's index in inorder is O(n) per call, making the algorithm O(n^2). The hash map turns each lookup into O(1).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →