Skip to main content

64. Construct Binary Tree from Preorder and Inorder Traversal

mediumAsked at Workday

Reconstruct a binary tree from its preorder and inorder traversals. Workday uses this to test tree-construction reasoning — same shape as rebuilding an org-chart from two parallel HRIS exports.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2025)— Workday SDE2 phone screen.

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 scan

First of preorder is root. Find root in inorder. Recurse on left and right.

Time
O(n^2) worst case
Space
O(n)
// indexOf is O(n); total can be quadratic on skewed trees

Tradeoff: Easy to write but quadratic worst case.

2. Recursive with inorder index map

Precompute inorder value -> index map. Use indices into preorder and inorder ranges; no slicing.

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

Tradeoff: O(n) overall via the precomputed map. preIdx is shared state — left subtree must be built before right (preorder root-left-right).

Workday-specific tips

Workday grades for the O(n) optimization. The precomputed inorder map is the key. Also: emphasize that left subtree MUST be built before right because preIdx is shared state (preorder visits root, then left, then right).

Common mistakes

  • Slicing arrays on each recursive call — O(n^2) and lots of allocation.
  • Building right before left — preIdx gets out of order.
  • Forgetting the inorder map and using indexOf — quadratic.

Follow-up questions

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

  • From Inorder and Postorder (LC 106) — similar but root is from end of postorder.
  • Validate uniqueness of values — required for the lookup map.
  • What if values can repeat?

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 precompute inorder map?

Each recursive call needs to locate the root in the inorder. indexOf is O(n). The map makes lookup O(1).

Why left before right?

preIdx is shared. Preorder is root-left-right. After consuming the root, the next preorder entry belongs to the left subtree — must recurse there first.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →