Skip to main content

76. Construct Binary Tree from Preorder and Inorder Traversal

mediumAsked at Ola

Rebuild a binary tree from its preorder and inorder traversals.

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. Assume all values are unique.

Constraints

  • 1 <= preorder.length <= 3000
  • preorder.length == inorder.length
  • All values 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. Slice and search

Take preorder[0] as root, find it in inorder, recurse on subarrays.

Time
O(n^2)
Space
O(n^2)
const build = (pre, inord) => {
  if (!pre.length) return null;
  const v = pre[0];
  const i = inord.indexOf(v);
  return { val: v, left: build(pre.slice(1, i+1), inord.slice(0, i)), right: build(pre.slice(i+1), inord.slice(i+1)) };
};

Tradeoff:

2. Index map with bounds

Build a value->index map of inorder; recursively reconstruct by passing index ranges only.

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

Tradeoff:

Ola-specific tips

Ola asks this to verify that you reach for the index map over repeated slicing; tie it to rebuilding a corrupted dispatch tree from two ordered logs.

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 Ola interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →