Module 6 · Tree Construction

Construct Binary Tree from Preorder and Inorder Traversal

MediumProblem 18 of 24 9 min read ~25 min to solve LeetCode

TreeDepth-First SearchDivide and ConquerHash TableRecursion

Asked atAmazonMicrosoftGoogleMetaBloomberg

Problem Statement

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 original binary tree.

All values are unique, so each value can identify exactly one position in the inorder traversal.

Input

Two arrays: preorder, which visits root, left, right, and inorder, which visits left, root, right.

Output

The root of the reconstructed binary tree. The returned pointer shape should match the unique tree described by both traversals.

Constraints

•1 <= preorder.length <= 3000
•inorder.length == preorder.length
•-3000 <= preorder[i], inorder[i] <= 3000
•All values in preorder and inorder are unique
•preorder and inorder describe the same binary tree

Examples

Example 1

Input:

preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

Output: [3,9,20,null,null,15,7]

Explanation: Preorder starts with root 3. In inorder, values left of 3 form the left subtree [9], and values right of 3 form the right subtree [15,20,7]. Applying the same rule recursively gives children 9 and 20, with 15 and 7 under 20.

Example 2

Input:

preorder = [-1], inorder = [-1]

Output: [-1]

Explanation: The only preorder value is also the only inorder value, so the tree is a single node.

Learning Objectives

Explain why the first unused preorder value must be the root of the current subtree.
Use the root's inorder index to split left and right subtree ranges.
Avoid array slicing by passing inorder boundaries and advancing one preorder pointer.
Use a hash map to find each root position in O(1).

Intuition

Pattern Recognition

The signal is the pair preorder + inorder. Preorder gives the root before anything else in that subtree, because its order is root, left, right. Inorder does not tell you the root first, but once you know the root value, inorder tells you exactly which values belong to the left subtree and which belong to the right subtree.

That is why the two traversals complement each other. Preorder answers what is the next root? Inorder answers where does that root split the subtree? With unique values, a hash map from value to inorder index makes every split constant time. A moving preorder pointer then consumes roots in the same order the recursive construction needs them.

Common mistakes

×Searching the inorder array linearly inside every recursive call, which can turn the solution into O(n^2).
×Slicing arrays for every subtree instead of passing index boundaries.
×Advancing the preorder pointer after building children instead of immediately after choosing the root.
×Using preorder lengths incorrectly and assigning values from the right subtree to the left subtree.

Algorithm Explanation

Key idea

The first unused preorder value is the root of the current subtree. Find that value in inorder. Everything to its left in the current inorder window is the left subtree, and everything to its right is the right subtree. Then recursively build the left side first, followed by the right side, because preorder lists left-subtree roots before right-subtree roots.

Recursion walkthrough

Use preorder [3,9,20,15,7] and inorder [9,3,15,20,7]. The first preorder value is 3, so 3 is the root. In inorder, 3 splits the array into left side [9] and right side [15,20,7]. The next preorder value is 9, which becomes the root of the left window [9] and has no children. The next preorder value is 20, which becomes the root of the right window [15,20,7]. In inorder, 20 splits that window into [15] and [7], so 15 becomes its left child and 7 becomes its right child.

Algorithm

Build a hash map from each inorder value to its index.
Set preorderIndex to 0 so it always points at the next subtree root.
Define a recursive helper over an inorder window left..right.
If the window is empty, return null.
Read preorder[preorderIndex] as the root value, then advance preorderIndex.
Look up the root's inorder index to split the current window.
Recursively build the left subtree from the left window, then the right subtree from the right window.
Return the root node.

Solutions

Solution: Preorder pointer plus inorder index map

When to prefer this:

Use this whenever values are unique and both preorder and inorder traversals are available. It is the standard interview solution because it avoids repeated scans and avoids allocating sliced arrays.

Precompute value -> inorder index. Then keep one moving pointer into preorder. Each recursive call owns an inorder range. The pointer gives the root value for that range, and the map gives the split point. The helper creates the root, builds the left range, builds the right range, and returns the finished subtree.

Step-by-step

Store every inorder value's index in a hash map.
Start preorderIndex at 0.
For a recursive inorder range, return null when the range is empty.
Otherwise choose preorder[preorderIndex] as the root and advance the pointer.
Split the inorder range around that root's index.
Build the left child from the left range and the right child from the right range.
Return the root after both children are attached.

Time

O(n)

Space

O(n)

The hash map stores n indices and each node is created once. The recursion stack is O(h), which is O(n) in the worst case.

Java implementation

Loading…

Dry Run

Sample input

preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]. Track each recursive inorder window and the root consumed from preorder.

call	root	inorder window	left inorder	right inorder
build(0,4)	3	[9,3,15,20,7]	[9]	[15,20,7]
build(0,0)	9	[9]	empty	empty
build(2,4)	20	[15,20,7]	[15]	[7]
build(2,2)	15	[15]	empty	empty
build(4,4)	7	[7]	empty	empty

The preorder pointer moves in root order: 3, then 9, then 20, then 15, then 7. The inorder windows decide where each chosen root's left and right children can come from.

Interview Tips

Say the two traversal roles out loud: preorder selects the root, inorder splits the subtree. Then emphasize that the hash map is not for searching values in the tree; it is for avoiding O(n) scans of inorder during recursion. If asked about duplicates, explain that this exact reconstruction is no longer uniquely determined without additional identity information.

Likely follow-ups

What changes if values are not unique?
Can you implement the same logic without global fields by passing indices through helper arguments?
How would you construct a tree from preorder and postorder when the tree is full?
How would you serialize the constructed tree to verify it in tests?

Key Takeaways

Preorder's first unused value is the current subtree root.
Inorder splits a known root into left-subtree values and right-subtree values.
A value-to-index map turns every split into O(1) work.
Passing index boundaries is cleaner and faster than slicing traversal arrays.

Reusable template: Traversal reconstruction: use one traversal to choose the root, use inorder to split the range, and recurse on the resulting left and right windows.