66. Construct Binary Tree from Preorder and Inorder Traversal

mediumAsked at Reddit

Rebuild a binary tree from preorder and inorder traversals. Reddit uses this to test tree-recursion with index management — the same skill used in their comment-tree audit where they must reconstruct the original tree from serialized snapshots.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

Source citations

Public interview reports confirming this problem appears in Reddit loops.

Glassdoor (2026-Q1)— Reddit comments-team on-site question.

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.
preorder is guaranteed to be the preorder traversal of the tree.
inorder is guaranteed to be the inorder traversal of the tree.

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 slice (naive)

First element of preorder = root. Split inorder around the root; recurse on the two halves.

Time: O(n^2)
Space: O(n^2)

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: indexOf is O(n) per call; slice copies are wasteful.

2. Hash map + index pointers (optimal)

Map inorder value -> index. Recurse with (preStart, inStart, inEnd) pointers.

Time: O(n)
Space: O(n)

function buildTree(preorder, inorder) {
  const idx = new Map();
  inorder.forEach((v, i) => idx.set(v, i));
  let pre = 0;
  function build(inStart, inEnd) {
    if (inStart > inEnd) return null;
    const val = preorder[pre++];
    const mid = idx.get(val);
    const node = { val, left: null, right: null };
    node.left = build(inStart, mid - 1);
    node.right = build(mid + 1, inEnd);
    return node;
  }
  return build(0, inorder.length - 1);
}

Tradeoff: Linear. Index pointers avoid slicing; hash makes split O(1).

Reddit-specific tips

Reddit interviewers grade on the hashmap optimization. Bonus signal: connect to deserialization audits — given two serializations, you can reconstruct the original tree (or detect a tamper if they don't match).

Common mistakes

Using indexOf inside recursion (O(n^2)).
Slicing arrays in JavaScript (creates copies; O(n) per level).
Recursing right before left (must process left subtree first to keep preorder pointer aligned).

Follow-up questions

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

From inorder + postorder (LC 106).
From preorder + postorder (LC 889).
Serialize and deserialize 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 recurse left before right?

Preorder visits root, then all of left subtree, then all of right. Our pre pointer must process left first to be aligned.

What if values aren't unique?

Hash map breaks. Add tiebreak via index of first occurrence after preStart.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →