Loading…

mediumTreesLC #105Frequently asked

Construct Binary Tree from Preorder and Inorder Traversal

Q: How do you solve Construct Binary Tree from Preorder and Inorder Traversal using the Recursion with Linear Inorder Scan approach?

When to use it: State it first to establish the core idea cleanly, then note the repeated scan makes it O(n²) and motivate the hash map. This is the algorithm in its most transparent form, before optimization. It directly encodes what the two traversals mean. **Step 1 — preorder gives the root.** Preorder is root, then left subtree, then right subtree. So the first element of the current preorder range is this subtree's root. Create that node. **Step 2 — inorder splits the children.** Inorder is left subtree, then root, then right subtree. Scan inorder to find the root's position `mid`. Everything before `mid` is the left subtree's inorder; everything after is the right subtree's inorder. The *number* of elements before `mid` also tells us how many leading preorder elements belong to the left subtree. **Step 3 — recurse.** Build the left child from the left slices and the right child from the right slices. Base case: an empty range yields null. **Why it's O(n²).** Correct, but the `find the root in inorder` scan is O(n) and runs once per node. A degenerate (chain) tree forces n scans of length up to n → O(n²). The fix is to precompute every value's inorder index once. Time complexity: O(n²). Space complexity: O(n).

Q: How do you solve Construct Binary Tree from Preorder and Inorder Traversal using the Hash Map of Inorder Indices + Preorder Pointer (Optimal) approach?

When to use it: The answer they want. 'Precompute value→inorder index for O(1) splits, and carry one advancing preorder index.' Two changes turn the O(n²) draft into a clean linear solution. **Change 1 — O(1) root location.** Before recursing, build a hash map `idx` mapping every value to its position in inorder. Finding where the root sits in inorder is now a single lookup, not a scan. This alone removes the quadratic factor. **Change 2 — a single advancing preorder pointer.** Rather than computing preorder sub-ranges, keep one shared index `preIndex` that starts at 0 and increments each time we take a root. Here's why that works: preorder lists a subtree as root, then its *entire* left subtree, then its *entire* right subtree. If we always build the left child before the right child, the pointer naturally walks the left subtree to completion before it reaches the first node of the right subtree. So consuming `preorder[preIndex++]` as the next root is always correct — the recursion order keeps the pointer synchronized. **The recursion bounds.** We now recurse over *inorder* index ranges `[inLo, inHi]`. The current root's inorder position `mid = idx[rootVal]` splits the range: `[inLo, mid-1]` is the left subtree, `[mid+1, inHi]` is the right. An empty range (`inLo > inHi`) returns null. **Why left strictly before right.** The shared pointer is order-sensitive. Build right first and you'd hand the right subtree the preorder elements that actually belong to the left subtree — the tree comes out scrambled. The left-then-right order is not a style choice; it's required for correctness. **Why no array slicing.** Passing index ranges and a shared pointer avoids creating O(n) sub-arrays at every level (which would reintroduce O(n²) work and memory churn). We allocate exactly one node per value and nothing else. Time complexity: O(n). Space complexity: O(n).

LCPractice

Trees & BST · 12 of 41 · 9 min

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.

All values in the tree are unique.

In plain English

We reverse-engineer a tree from two of its traversals. Preorder visits root then left then right, so its first value is the overall root. Inorder visits left then root then right, so once we know the root we can split inorder into the nodes left of the root (left subtree) and right of the root (right subtree). Repeating this on each half rebuilds the whole 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]
Note: Root 3 splits inorder into [9] (left) and [15,20,7] (right). Recursing: 9 is a leaf; 20 is the next root with [15] left and [7] right.

Example 2

Input: preorder = [-1], inorder = [-1]
Output: [-1]
Note: Single node tree.

Example 3

Input: preorder = [1,2,3], inorder = [3,2,1]
Output: [1,2,3] as a left-only chain (1→2→3)
Note: Root 1 has nothing to its right in inorder, so its entire subtree is on the left, forming a left-leaning chain.

Constraints

1 ≤ preorder.length ≤ 3000
inorder.length == preorder.length
-3000 ≤ preorder[i], inorder[i] ≤ 3000
preorder and inorder consist of unique values
inorder is a permutation of preorder; both describe the same valid binary tree

Clarifying questions4First question: Are all values unique?Explore questions

Q1.Are all values unique?
Yes — that's essential. We locate the root by value in inorder, which is only unambiguous when values are unique.
Q2.Do both arrays describe the same tree and have equal length?
Yes. inorder is a permutation of preorder, so every preorder root has a defined position in inorder.
Q3.Could the input be invalid (not a real tree)?
We can assume valid, consistent traversals. We won't add validation unless asked.
Q4.Should I slice the arrays or pass index ranges?
Pass index ranges and a shared preorder pointer. Slicing copies sub-arrays each call and adds O(n) overhead per level.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Preorder's first element is always the root. Find that root inside inorder: everything to its left is the left subtree, everything to its right is the right subtree, and the count of those left elements tells you how to split preorder too. Recurse. Pre-build a hash map from value → inorder index so each root lookup is O(1), and advance a single global preorder pointer. O(n) time, O(n) space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you understand what each traversal encodes (preorder = root-first, inorder = left/root/right) and can combine them recursively — plus whether you optimize the repeated root lookup with a hash map.

Where candidates slip

Re-scanning inorder for the root every call (O(n²)), mis-slicing the preorder ranges, or recursing right before left so the preorder pointer desynchronizes.

How to stand out

Use a value→index map for O(1) splits, drive recursion with a single preorder index instead of slicing arrays (avoids O(n) copies), and explain why left must be built before right.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Recursion with Linear Inorder Scan	`O(n²)`	`O(n)`	State it first to establish the core idea cleanly, then note the repeated scan makes it O(n²) and motivate the hash map.	Read
2	Hash Map of Inorder Indices + Preorder Pointer (Optimal)Optimal	`O(n)`	`O(n)`	The answer they want. 'Precompute value→inorder index for O(1) splits, and carry one advancing preorder index.'	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewRebuild tree from preorder + inorderO(1) root lookup in inorder?Yes (hash map)No (linear scan)Explore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Recursion with Linear Inorder Scan

TimeO(n²)SpaceO(n)

State it first to establish the core idea cleanly, then note the repeated scan makes it O(n²) and motivate the hash map.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

What does the very first element of a preorder traversal tell you about the tree?

2Hint 2Explore hint

Once you know the root, where is it in the inorder array, and what do the elements to its left and right represent?

3Hint 3Explore hint

Recurse: the left part of inorder is the left subtree, the right part is the right subtree. Finding the root in inorder each time is a linear scan.

A · Core idea

This is the algorithm in its most transparent form, before optimization. It directly encodes what the two traversals mean.

Step 1 — preorder gives the root. Preorder is root, then left subtree, then right subtree. So the first element of the current preorder range is this subtree's root. Create that node.

Step 2 — inorder splits the children. Inorder is left subtree, then root, then right subtree. Scan inorder to find the root's position mid. Everything before mid is the left subtree's inorder; everything after is the right subtree's inorder. The number of elements before mid also tells us how many leading preorder elements belong to the left subtree.

Step 3 — recurse. Build the left child from the left slices and the right child from the right slices. Base case: an empty range yields null.

Why it's O(n²). Correct, but the find the root in inorder scan is O(n) and runs once per node. A degenerate (chain) tree forces n scans of length up to n → O(n²). The fix is to precompute every value's inorder index once.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

root = 3

find 3 in inorder at index 1 → left=[9], right=[15,20,7]

Stateleft preorder=[9], right preorder=[20,15,7]

Final result[3,9,20,null,null,15,7]

C · Code with teaching comments

Reference implementation preview// Definition for a binary tree node. // class TreeNode { // int val; // TreeNode left; // TreeNode right;Explore the full code

solution.javaJava

Recursion with Linear Inorder Scan — reference

4 teaching notes

1
// Definition for a binary tree node.
2
// class TreeNode {
3
//     int val;
4
//     TreeNode left;
5
//     TreeNode right;
6
//     TreeNode(int x) { val = x; }
7
// }
8
public TreeNode buildTree(int[] preorder, int[] inorder) {
9
    return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
10
}
11
 
12
private TreeNode build(int[] preorder, int preLo, int preHi,
13
                       int[] inorder, int inLo, int inHi) {
14
    if (preLo > preHi) {
15
        return null;
16
    }
17
    // First element of this preorder range is the subtree's root.
18
    int rootVal = preorder[preLo];
19
    TreeNode root = new TreeNode(rootVal);
20
    int mid = inLo;
21
    // Locate the root in inorder — this O(n) scan is what makes the whole thing O(n²).
22
    while (inorder[mid] != rootVal) {
23
        mid++; // linear scan → O(n) per call
24
    }
25
    // Count of left-subtree nodes; used to split the preorder range too.
26
    int leftSize = mid - inLo;
27
    root.left = build(preorder, preLo + 1, preLo + leftSize, inorder, inLo, mid - 1);
28
    root.right = build(preorder, preLo + leftSize + 1, preHi, inorder, mid + 1, inHi);
29
    return root;
30
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.30 lines

D · Why it works and complexityO(n²) timeO(n) spaceOpen the invariant and proofExplore the proof

The two traversals are complementary: preorder names the root, inorder partitions the rest. Internalizing 'who is the root' vs 'how do the others split' is what makes every variant (postorder+inorder, etc.) fall out naturally.

ComplexityO(n²) time, O(n) space — Each of the n recursive calls scans inorder to find the root in O(n) worst case → O(n²) time. Recursion depth and the slices add O(n) space.

E · Edge cases and pitfalls3Re-scanning inorder every call → O(n²).Explore edge cases

Pitfalls

Re-scanning inorder every call → O(n²).
Mis-computing the preorder split offsets (off-by-one on leftSize).
Slicing arrays instead of passing indices, adding O(n) copy cost per node.

03.2

Approach 2 of 2 · Optimal

Hash Map of Inorder Indices + Preorder Pointer (Optimal)

TimeO(n)SpaceO(n)

The answer they want. 'Precompute value→inorder index for O(1) splits, and carry one advancing preorder index.'

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The slow part is finding the root in inorder each time. Can you make that lookup O(1)?

2Hint 2Explore hint

Build a hash map from each value to its index in inorder once, up front. Now splitting is instant.

3Hint 3Explore hint

Instead of slicing preorder, keep a single index that advances every time you consume a root. Because preorder is root→left→right, recursing left before right consumes elements in exactly the right order.

A · Core idea

Two changes turn the O(n²) draft into a clean linear solution.

Change 1 — O(1) root location. Before recursing, build a hash map idx mapping every value to its position in inorder. Finding where the root sits in inorder is now a single lookup, not a scan. This alone removes the quadratic factor.

Change 2 — a single advancing preorder pointer. Rather than computing preorder sub-ranges, keep one shared index preIndex that starts at 0 and increments each time we take a root. Here's why that works: preorder lists a subtree as root, then its entire left subtree, then its entire right subtree. If we always build the left child before the right child, the pointer naturally walks the left subtree to completion before it reaches the first node of the right subtree. So consuming preorder[preIndex++] as the next root is always correct — the recursion order keeps the pointer synchronized.

The recursion bounds. We now recurse over inorder index ranges [inLo, inHi]. The current root's inorder position mid = idx[rootVal] splits the range: [inLo, mid-1] is the left subtree, [mid+1, inHi] is the right. An empty range (inLo > inHi) returns null.

Why left strictly before right. The shared pointer is order-sensitive. Build right first and you'd hand the right subtree the preorder elements that actually belong to the left subtree — the tree comes out scrambled. The left-then-right order is not a style choice; it's required for correctness.

Why no array slicing. Passing index ranges and a shared pointer avoids creating O(n) sub-arrays at every level (which would reintroduce O(n²) work and memory churn). We allocate exactly one node per value and nothing else.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Interactive diagram

The reconstructed tree

preIndex=0 → root 3

Active call / nodeSupporting contextReturned stateNot active

Root 3 from preorder; inorder splits [9] left and [15,20,7] right; 20 then splits into 15 and 7.

Final result[3,9,20,null,null,15,7]

C · Code with teaching comments

solution.javaJava

Hash Map of Inorder Indices + Preorder Pointer (Optimal) — optimal

4 teaching notes

1
// Definition for a binary tree node.
2
// class TreeNode {
3
//     int val;
4
//     TreeNode left;
5
//     TreeNode right;
6
//     TreeNode(int x) { val = x; }
7
// }
8
private int preIndex;
9
private Map<Integer, Integer> inIndex;
10
 
11
public TreeNode buildTree(int[] preorder, int[] inorder) {
12
    preIndex = 0;
13
    inIndex = new HashMap<>();
14
    for (int i = 0; i < inorder.length; i++) {
15
        // Precompute value→inorder index once → O(1) root location later.
16
        inIndex.put(inorder[i], i);
17
    }
18
    return build(preorder, 0, inorder.length - 1);
19
}
20
 
21
private TreeNode build(int[] preorder, int inLo, int inHi) {
22
    if (inLo > inHi) {
23
        return null;
24
    }
25
    // Take the next preorder element as the root and advance the shared pointer.
26
    int rootVal = preorder[preIndex++];
27
    TreeNode root = new TreeNode(rootVal);
28
    // O(1) lookup of the root's inorder position to split left/right.
29
    int mid = inIndex.get(rootVal);
30
    root.left = build(preorder, inLo, mid - 1);   // left BEFORE right
31
    root.right = build(preorder, mid + 1, inHi);
32
    return root;
33
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.33 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

The map removes the search cost and the shared preorder pointer removes the bookkeeping cost. Together they express the structure of the traversals directly: 'next preorder element is the next root; its inorder index tells me how the rest divides'. This index-map + global-pointer template reappears in the postorder+inorder variant (just walk the pointer from the end and build right before left).

ComplexityO(n) time, O(n) space — The map is built in O(n). Each node is created once with O(1) lookup work → O(n) total time. The map, recursion stack (O(h)), and output tree are O(n) space.

E · Edge cases and pitfalls6preorder = [1], inorder = [1] — Range [0,0]: root 1, then left [0,-1] and right [1,0] both empty → single node.Explore edge cases

Edge cases handled

preorder = [1], inorder = [1]Range [0,0]: root 1, then left [0,-1] and right [1,0] both empty → single node.
preorder = [1,2,3], inorder = [3,2,1]Every root has an empty right range → a left-leaning chain 1→2→3.
preorder = [1,2,3], inorder = [1,2,3]Every root has an empty left range → a right-leaning chain 1→2→3.

Pitfalls

Recursing right before left — desyncs the shared preorder pointer and scrambles the tree.
Forgetting to reset preIndex between calls (Java instance field) — stale state on a second invocation.
Rebuilding the index map inside the recursion instead of once up front.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code preview// Definition for a binary tree node. // class TreeNode { // int val; // TreeNode left; // TreeNode right;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Right-before-left with a shared pointer

A single advancing preorder index assumes the left subtree is consumed before the right. Building the right child first feeds it the left subtree's preorder elements, producing a wrong tree.

Explore the code comparison

Don't write this

root.right = build(mid + 1, in_hi)   # consumes left subtree's preorder!
root.left  = build(in_lo, mid - 1)

Write this instead

root.left  = build(in_lo, mid - 1)   # left first
root.right = build(mid + 1, in_hi)

Searching inorder every call

Finding the root with a linear scan is O(n) and runs per node, giving O(n²). A precomputed value→index map makes each lookup O(1) and the whole build O(n).

Explore the code comparison

Don't write this

int mid = inLo;
while (inorder[mid] != rootVal) mid++;  // O(n) every call

Write this instead

// built once before recursion:
// for (int i = 0; i < inorder.length; i++) inIndex.put(inorder[i], i);
int mid = inIndex.get(rootVal);          // O(1)

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Divide & conquer on traversal arrays (root-from-preorder, split-by-inorder)

Code pattern to memorize

idx = {v: i for i, v in enumerate(inorder)}
self.pre = 0
def build(lo, hi):           # inorder bounds
    if lo > hi: return None
    root_val = preorder[self.pre]; self.pre += 1
    root = TreeNode(root_val)
    mid = idx[root_val]
    root.left  = build(lo, mid - 1)   # left BEFORE right (preorder!)
    root.right = build(mid + 1, hi)
    return root

Rules to remember

1Preorder[0] (then the next unused preorder element) is always the current subtree's root.
2Locate the root in inorder to split into left subtree (before) and right subtree (after).
3Recurse left before right — preorder consumes the entire left subtree before the right.
4Build a value → inorder index hash map up front so each split is O(1) instead of an O(n) scan.
5Assumes unique values (so the map lookup is unambiguous) and that both traversals describe the same tree.

Use this pattern when

Rebuilding a tree from two traversal orders (pre+in, post+in)
Any divide-and-conquer where one array names the root and another splits the children
Problems where 'first/last element is the root' plus 'find it to partition' applies
Serialization/deserialization variants of trees

Choose another pattern when

Only one traversal given (e.g. just preorder) → ambiguous unless it's a BST or has null markers
Values are NOT unique → you can't uniquely locate the root in inorder; need positions/markers
Preorder + postorder alone → tree isn't unique unless it's full (every node has 0 or 2 children)
You need O(1) extra space → recursion + map is O(n); a different encoding is required

Interview takeaway

Two traversals pin down a unique tree because preorder hands you the root and inorder tells you how the remaining nodes split into left and right. The hash-map-of-indices plus a single advancing preorder pointer turns the naive O(n²) recursion into a clean O(n) divide and conquer.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternDivide and conquer on traversal arrays. One traversal names the root; the other (or the BST ordering) tells you how the rest splits into left and right. The value→index hash map plus a single advancing pointer is the canonical O(n) template, shared with the inorder+postorder and serialize/deserialize variants.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Construct Binary Tree from Inorder and Postorder Traversal
Coming soon
Postorder's LAST element is the root; walk the pointer backward and build right before left.
Construct Binary Tree from Preorder and Postorder Traversal
Coming soon
Not unique in general — only well-defined for full binary trees.
Serialize and Deserialize Binary Tree
Coming soon
Preorder with explicit null markers makes a single traversal sufficient to rebuild.
Construct Binary Search Tree from Preorder Traversal
Coming soon
For a BST, the ordering replaces inorder — split by value bounds, no second array needed.

Same pattern

←

Kth Smallest Element in a BST

Continue · Next problem

Binary Tree Maximum Path Sum

mediumTreesLC #105Frequently asked

Construct Binary Tree from Preorder and Inorder Traversal

LCPractice

Trees & BST · 12 of 41 · 9 min

All values in the tree are unique.

In plain English

Examples

Example 1

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
Note: Root 3 splits inorder into [9] (left) and [15,20,7] (right). Recursing: 9 is a leaf; 20 is the next root with [15] left and [7] right.

Example 2

Input: preorder = [-1], inorder = [-1]
Output: [-1]
Note: Single node tree.

Example 3

Input: preorder = [1,2,3], inorder = [3,2,1]
Output: [1,2,3] as a left-only chain (1→2→3)
Note: Root 1 has nothing to its right in inorder, so its entire subtree is on the left, forming a left-leaning chain.

Constraints

1 ≤ preorder.length ≤ 3000
inorder.length == preorder.length
-3000 ≤ preorder[i], inorder[i] ≤ 3000
preorder and inorder consist of unique values
inorder is a permutation of preorder; both describe the same valid binary tree

Clarifying questions4First question: Are all values unique?Explore questions

Q1.Are all values unique?
Yes — that's essential. We locate the root by value in inorder, which is only unambiguous when values are unique.
Q2.Do both arrays describe the same tree and have equal length?
Yes. inorder is a permutation of preorder, so every preorder root has a defined position in inorder.
Q3.Could the input be invalid (not a real tree)?
We can assume valid, consistent traversals. We won't add validation unless asked.
Q4.Should I slice the arrays or pass index ranges?
Pass index ranges and a shared preorder pointer. Slicing copies sub-arrays each call and adds O(n) overhead per level.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

Re-scanning inorder for the root every call (O(n²)), mis-slicing the preorder ranges, or recursing right before left so the preorder pointer desynchronizes.

How to stand out

Use a value→index map for O(1) splits, drive recursion with a single preorder index instead of slicing arrays (avoids O(n) copies), and explain why left must be built before right.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Recursion with Linear Inorder Scan	`O(n²)`	`O(n)`	State it first to establish the core idea cleanly, then note the repeated scan makes it O(n²) and motivate the hash map.	Read
2	Hash Map of Inorder Indices + Preorder Pointer (Optimal)Optimal	`O(n)`	`O(n)`	The answer they want. 'Precompute value→inorder index for O(1) splits, and carry one advancing preorder index.'	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Recursion with Linear Inorder Scan

TimeO(n²)SpaceO(n)

State it first to establish the core idea cleanly, then note the repeated scan makes it O(n²) and motivate the hash map.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

What does the very first element of a preorder traversal tell you about the tree?

2Hint 2Explore hint

Once you know the root, where is it in the inorder array, and what do the elements to its left and right represent?

3Hint 3Explore hint

Recurse: the left part of inorder is the left subtree, the right part is the right subtree. Finding the root in inorder each time is a linear scan.

A · Core idea

This is the algorithm in its most transparent form, before optimization. It directly encodes what the two traversals mean.

Step 1 — preorder gives the root. Preorder is root, then left subtree, then right subtree. So the first element of the current preorder range is this subtree's root. Create that node.

Step 3 — recurse. Build the left child from the left slices and the right child from the right slices. Base case: an empty range yields null.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

root = 3

find 3 in inorder at index 1 → left=[9], right=[15,20,7]

Stateleft preorder=[9], right preorder=[20,15,7]

Final result[3,9,20,null,null,15,7]

C · Code with teaching comments

Reference implementation preview// Definition for a binary tree node. // class TreeNode { // int val; // TreeNode left; // TreeNode right;Explore the full code

solution.javaJava

Recursion with Linear Inorder Scan — reference

4 teaching notes

1
// Definition for a binary tree node.
2
// class TreeNode {
3
//     int val;
4
//     TreeNode left;
5
//     TreeNode right;
6
//     TreeNode(int x) { val = x; }
7
// }
8
public TreeNode buildTree(int[] preorder, int[] inorder) {
9
    return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
10
}
11
 
12
private TreeNode build(int[] preorder, int preLo, int preHi,
13
                       int[] inorder, int inLo, int inHi) {
14
    if (preLo > preHi) {
15
        return null;
16
    }
17
    // First element of this preorder range is the subtree's root.
18
    int rootVal = preorder[preLo];
19
    TreeNode root = new TreeNode(rootVal);
20
    int mid = inLo;
21
    // Locate the root in inorder — this O(n) scan is what makes the whole thing O(n²).
22
    while (inorder[mid] != rootVal) {
23
        mid++; // linear scan → O(n) per call
24
    }
25
    // Count of left-subtree nodes; used to split the preorder range too.
26
    int leftSize = mid - inLo;
27
    root.left = build(preorder, preLo + 1, preLo + leftSize, inorder, inLo, mid - 1);
28
    root.right = build(preorder, preLo + leftSize + 1, preHi, inorder, mid + 1, inHi);
29
    return root;
30
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.30 lines

D · Why it works and complexityO(n²) timeO(n) spaceOpen the invariant and proofExplore the proof

ComplexityO(n²) time, O(n) space — Each of the n recursive calls scans inorder to find the root in O(n) worst case → O(n²) time. Recursion depth and the slices add O(n) space.

E · Edge cases and pitfalls3Re-scanning inorder every call → O(n²).Explore edge cases

Pitfalls

Re-scanning inorder every call → O(n²).
Mis-computing the preorder split offsets (off-by-one on leftSize).
Slicing arrays instead of passing indices, adding O(n) copy cost per node.

03.2

Approach 2 of 2 · Optimal

Hash Map of Inorder Indices + Preorder Pointer (Optimal)

TimeO(n)SpaceO(n)

The answer they want. 'Precompute value→inorder index for O(1) splits, and carry one advancing preorder index.'

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The slow part is finding the root in inorder each time. Can you make that lookup O(1)?

2Hint 2Explore hint

Build a hash map from each value to its index in inorder once, up front. Now splitting is instant.

3Hint 3Explore hint

A · Core idea

Two changes turn the O(n²) draft into a clean linear solution.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Interactive diagram

The reconstructed tree

preIndex=0 → root 3

Active call / nodeSupporting contextReturned stateNot active

Root 3 from preorder; inorder splits [9] left and [15,20,7] right; 20 then splits into 15 and 7.

Final result[3,9,20,null,null,15,7]

C · Code with teaching comments

solution.javaJava

Hash Map of Inorder Indices + Preorder Pointer (Optimal) — optimal

4 teaching notes

1
// Definition for a binary tree node.
2
// class TreeNode {
3
//     int val;
4
//     TreeNode left;
5
//     TreeNode right;
6
//     TreeNode(int x) { val = x; }
7
// }
8
private int preIndex;
9
private Map<Integer, Integer> inIndex;
10
 
11
public TreeNode buildTree(int[] preorder, int[] inorder) {
12
    preIndex = 0;
13
    inIndex = new HashMap<>();
14
    for (int i = 0; i < inorder.length; i++) {
15
        // Precompute value→inorder index once → O(1) root location later.
16
        inIndex.put(inorder[i], i);
17
    }
18
    return build(preorder, 0, inorder.length - 1);
19
}
20
 
21
private TreeNode build(int[] preorder, int inLo, int inHi) {
22
    if (inLo > inHi) {
23
        return null;
24
    }
25
    // Take the next preorder element as the root and advance the shared pointer.
26
    int rootVal = preorder[preIndex++];
27
    TreeNode root = new TreeNode(rootVal);
28
    // O(1) lookup of the root's inorder position to split left/right.
29
    int mid = inIndex.get(rootVal);
30
    root.left = build(preorder, inLo, mid - 1);   // left BEFORE right
31
    root.right = build(preorder, mid + 1, inHi);
32
    return root;
33
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.33 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(n) space — The map is built in O(n). Each node is created once with O(1) lookup work → O(n) total time. The map, recursion stack (O(h)), and output tree are O(n) space.

E · Edge cases and pitfalls6preorder = [1], inorder = [1] — Range [0,0]: root 1, then left [0,-1] and right [1,0] both empty → single node.Explore edge cases

Edge cases handled

preorder = [1], inorder = [1]Range [0,0]: root 1, then left [0,-1] and right [1,0] both empty → single node.
preorder = [1,2,3], inorder = [3,2,1]Every root has an empty right range → a left-leaning chain 1→2→3.
preorder = [1,2,3], inorder = [1,2,3]Every root has an empty left range → a right-leaning chain 1→2→3.

Pitfalls

Recursing right before left — desyncs the shared preorder pointer and scrambles the tree.
Forgetting to reset preIndex between calls (Java instance field) — stale state on a second invocation.
Rebuilding the index map inside the recursion instead of once up front.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code preview// Definition for a binary tree node. // class TreeNode { // int val; // TreeNode left; // TreeNode right;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Right-before-left with a shared pointer

A single advancing preorder index assumes the left subtree is consumed before the right. Building the right child first feeds it the left subtree's preorder elements, producing a wrong tree.

Explore the code comparison

Don't write this

root.right = build(mid + 1, in_hi)   # consumes left subtree's preorder!
root.left  = build(in_lo, mid - 1)

Write this instead

root.left  = build(in_lo, mid - 1)   # left first
root.right = build(mid + 1, in_hi)

Searching inorder every call

Finding the root with a linear scan is O(n) and runs per node, giving O(n²). A precomputed value→index map makes each lookup O(1) and the whole build O(n).

Explore the code comparison

Don't write this

int mid = inLo;
while (inorder[mid] != rootVal) mid++;  // O(n) every call

Write this instead

// built once before recursion:
// for (int i = 0; i < inorder.length; i++) inIndex.put(inorder[i], i);
int mid = inIndex.get(rootVal);          // O(1)

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Divide & conquer on traversal arrays (root-from-preorder, split-by-inorder)

Code pattern to memorize

idx = {v: i for i, v in enumerate(inorder)}
self.pre = 0
def build(lo, hi):           # inorder bounds
    if lo > hi: return None
    root_val = preorder[self.pre]; self.pre += 1
    root = TreeNode(root_val)
    mid = idx[root_val]
    root.left  = build(lo, mid - 1)   # left BEFORE right (preorder!)
    root.right = build(mid + 1, hi)
    return root

Rules to remember

1Preorder[0] (then the next unused preorder element) is always the current subtree's root.
2Locate the root in inorder to split into left subtree (before) and right subtree (after).
3Recurse left before right — preorder consumes the entire left subtree before the right.
4Build a value → inorder index hash map up front so each split is O(1) instead of an O(n) scan.
5Assumes unique values (so the map lookup is unambiguous) and that both traversals describe the same tree.

Use this pattern when

Rebuilding a tree from two traversal orders (pre+in, post+in)
Any divide-and-conquer where one array names the root and another splits the children
Problems where 'first/last element is the root' plus 'find it to partition' applies
Serialization/deserialization variants of trees

Choose another pattern when

Only one traversal given (e.g. just preorder) → ambiguous unless it's a BST or has null markers
Values are NOT unique → you can't uniquely locate the root in inorder; need positions/markers
Preorder + postorder alone → tree isn't unique unless it's full (every node has 0 or 2 children)
You need O(1) extra space → recursion + map is O(n); a different encoding is required

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Construct Binary Tree from Inorder and Postorder Traversal
Coming soon
Postorder's LAST element is the root; walk the pointer backward and build right before left.
Construct Binary Tree from Preorder and Postorder Traversal
Coming soon
Not unique in general — only well-defined for full binary trees.
Serialize and Deserialize Binary Tree
Coming soon
Preorder with explicit null markers makes a single traversal sufficient to rebuild.
Construct Binary Search Tree from Preorder Traversal
Coming soon
For a BST, the ordering replaces inorder — split by value bounds, no second array needed.

Same pattern

←

Kth Smallest Element in a BST

Continue · Next problem

Binary Tree Maximum Path Sum