Skip to main content

66. Construct Binary Tree from Preorder and Inorder Traversal

mediumAsked at Salesforce

Reconstruct a binary tree given its preorder and inorder traversals. Salesforce uses this to test recursive tree construction with index management.

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

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

  • Glassdoor (2026-Q1)— Salesforce uses tree reconstruction in their metadata-deployment pipeline.
  • LeetCode Discuss (2025-09)— Tests recursive tree construction with hashmap optimization.

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 indexOf

preorder[0] is root. Find its index in inorder. Left subtree is everything before; right subtree is after.

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: indexOf is O(n) per call; total O(n^2). Plus slice allocates.

2. Indices + hash map lookup

Build index map of inorder values. Recurse on pre/in index ranges, not slices.

Time
O(n)
Space
O(n)
function buildTree(preorder, inorder) {
  const map = new Map();
  inorder.forEach((v, i) => map.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 inMid = map.get(val);
    node.left = build(inLo, inMid - 1);
    node.right = build(inMid + 1, inHi);
    return node;
  }
  return build(0, inorder.length - 1);
}

Tradeoff: O(n) total. The closure preIdx walks the preorder array linearly. The map gives O(1) lookups for the inorder split.

Salesforce-specific tips

Salesforce uses tree reconstruction in their metadata-deployment pipeline (rebuilding org hierarchy from serialized form). They grade on whether you use the index-range + hashmap optimization. Bonus signal: discuss that LC 106 (postorder + inorder) uses the same algorithm with postorder walked in reverse.

Common mistakes

  • Using slices recursively — turns O(n) into O(n^2) due to allocation.
  • Using indexOf in the recursive call — O(n^2).
  • Forgetting that preorder is walked linearly — the next root is always preorder[preIdx].

Follow-up questions

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

  • Construct Binary Tree from Inorder and Postorder Traversal (LC 106).
  • Serialize and Deserialize Binary Tree (LC 297).
  • Reconstruct from preorder only (must be a BST).

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 walk preorder linearly?

Preorder visits root before subtrees. The next preorder value is always the root of the next subtree to be built (left first, then right).

Why use the inorder map?

To find the root's split position in O(1). Without it, indexOf gives O(n) per call, total O(n^2).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →