72. Construct Binary Tree from Preorder and Inorder Traversal
mediumAsked at PlaidReconstruct a binary tree from its preorder and inorder traversals. Plaid asks this because deserializing a tree from two stream snapshots (preorder = parent-first, inorder = sorted) is the same reconstruction primitive.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Plaid loops.
- Glassdoor (2025)— Plaid SWE III onsite — tree-reconstruction classic.
- LeetCode Discuss (2026)— Plaid construction problem.
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 <= 3000inorder.length == preorder.length-3000 <= preorder[i], inorder[i] <= 3000preorder and inorder consist of unique values.
Examples
Example 1
preorder = [3,9,20,15,7], inorder = [9,3,15,20,7][3,9,20,null,null,15,7]Example 2
preorder = [-1], inorder = [-1][-1]Approaches
1. Recursive with linear search
Root is preorder[0]. Find it in inorder; everything left is the left subtree, right is the right subtree. Recurse.
- Time
- O(n^2)
- Space
- O(n)
function buildTree(preorder, inorder) {
if (preorder.length === 0) return null;
const root = { val: preorder[0], left: null, right: null };
const i = inorder.indexOf(preorder[0]);
root.left = buildTree(preorder.slice(1, 1 + i), inorder.slice(0, i));
root.right = buildTree(preorder.slice(1 + i), inorder.slice(i + 1));
return root;
}Tradeoff: Clear but indexOf and slice make it quadratic.
2. Recursive with inorder index map
Pre-build a value-to-index map for inorder. Use indices instead of slicing.
- Time
- O(n)
- Space
- O(n)
function buildTree(preorder, inorder) {
const idx = new Map();
inorder.forEach((v, i) => idx.set(v, i));
let p = 0;
function go(lo, hi) {
if (lo > hi) return null;
const v = preorder[p++];
const m = idx.get(v);
const node = { val: v, left: null, right: null };
node.left = go(lo, m - 1);
node.right = go(m + 1, hi);
return node;
}
return go(0, inorder.length - 1);
}Tradeoff: Linear time. The index map collapses the O(n) lookup to O(1); using lo/hi indices avoids the O(n) slice.
Plaid-specific tips
Plaid grades this on whether you spot the O(n^2) trap. Bonus signal: explain why preorder gives root and inorder gives left/right partition. Connect to deserializing a category tree from two stream snapshots (top-down vs sorted) in their analytics pipeline.
Common mistakes
- Using slice() and indexOf in the recursive case — quadratic.
- Off-by-one on inorder index bounds (m - 1 vs m).
- Forgetting that preorder shrinks as we consume the global pointer p.
Follow-up questions
An interviewer at Plaid may pivot to one of these next:
- From postorder and inorder (LC 106).
- From preorder and postorder (LC 889).
- Serialize and deserialize a tree (LC 297).
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why does this need both traversals?
Preorder alone doesn't pin tree shape (siblings vs children are ambiguous). Inorder gives the left/right split for any given root.
Why is the global p pointer needed?
Each recursive call consumes the next preorder value. A global pointer is simpler than computing the offset for each subtree.