Skip to main content

20. Construct Binary Tree from Preorder and Inorder Traversal

mediumAsked at Chegg

Reconstruct a binary tree from two traversal orders — tests tree manipulation depth that Chegg uses for rebuilding content category hierarchies from index data.

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

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
  • preorder.length == inorder.length
  • -3000 <= preorder[i], inorder[i] <= 3000
  • All values in preorder and inorder are unique

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

For each root (preorder[0]), find its index in inorder via indexOf — O(n) per call leading to O(n^2) total.

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

Tradeoff:

2. Hash map for O(1) index lookups

Pre-build a map from inorder value to index; pass index boundaries instead of slicing arrays, reducing overall time to O(n).

Time
O(n)
Space
O(n)
function buildTree(preorder, inorder) {
  const idxMap = new Map();
  inorder.forEach((val, i) => idxMap.set(val, i));
  let preIdx = 0;
  function helper(lo, hi) {
    if (lo > hi) return null;
    const rootVal = preorder[preIdx++];
    const node = new TreeNode(rootVal);
    const mid = idxMap.get(rootVal);
    node.left = helper(lo, mid - 1);
    node.right = helper(mid + 1, hi);
    return node;
  }
  return helper(0, inorder.length - 1);
}

Tradeoff:

Chegg-specific tips

Chegg values seeing the O(n^2) → O(n) optimization with the hash map — explain why slicing creates new arrays and how boundary indices avoid that allocation.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →