← DSA Atlas
Dedicated problem page · #105

Construct Binary Tree from Preorder and Inorder

MediumTrees and Binary Search TreesPreorder root + inorder splitRecursive tree construction with an index map
Solve on LeetCode ↗
105
MediumTrees and Binary Search TreesRecursive tree construction with an index mapPreorder root + inorder split

Construct Binary Tree from Preorder and Inorder

Given two integer arrays preorder and inorder representing the preorder and inorder traversals of a binary tree with unique values, reconstruct and return the tree.

Open official problem prompt ↗
In plain English

Rebuild the unique binary tree that produced the given preorder and inorder traversals.

Picture it like this

Like reassembling a book from a table of contents (preorder tells you which chapter starts next) and an index (inorder tells you what falls before and after each chapter title).

Example
Input
preorder = [3, 9, 20, 15, 7], inorder = [9, 3, 15, 20, 7]
Output
[3, 9, 20, null, null, 15, 7]
Why
3 is the root; in inorder, 9 is left of 3 and [15,20,7] are right, matching the reconstructed tree.
Constraints
1 <= preorder.length <= 3000inorder.length == preorder.length-3000 <= values <= 3000preorder and inorder consist of unique valuesinorder is a permutation of preorder
Pattern lesson

See the pattern, then code

Preorder root + inorder split
Recognition clue

You are given preorder plus inorder of a tree with unique values — the textbook setup where the preorder head names the root and inorder splits left from right.

↗
Trees and Binary Search Trees

Hierarchies, subtree aggregation, path properties, or ordered tree queries.. The first element of preorder is always the current root; its position in inorder partitions inorder into the left subtree (before it) and right subtree (after it), and their sizes tell you how to slice preorder.

New words, made simpleKnow these before the algorithm
Preorder
Root, then left subtree, then right subtree — so the next unused element is always the current root.
Inorder
Left subtree, then root, then right subtree — the root's position separates left from right.
Index map
A dictionary from value to its inorder position, giving O(1) split lookups.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Slice arrays each call

index() search and array slicing per call make it quadratic in the worst case.

Find the root in inorder, then pass sliced sub-arrays for left and right.

Time O(n^2)Space O(n^2)
Best choiceIndex map + preorder pointer

Each node built in O(1) work beyond recursion; linear overall.

Precompute value-to-index, advance a single preorder pointer, and recurse on inorder bounds.

Time O(n)Space O(n)
The rule we keep true

Invariant

self.pre always points at the root of the subtree currently being built, and [left, right] delimits that subtree's span within inorder.

Why this is correct

Reasoning

Preorder visits roots before their subtrees, so consuming it left-to-right hands out roots in exactly the order the recursion needs them; inorder's root position correctly sizes the left subtree, ensuring the pointer lands on the right subtree's root next.

The algorithm in three movesSay these aloud before coding
1Map each inorder value to its index for O(1) lookup

root=3, inorder split: [9] | [15,20,7]

2Consume preorder left-to-right with a moving pointer for the next root

left of 3 -> 9

3Locate the root in inorder to find the split

right of 3 -> root 20, split [15] | [7]

4Recursively build the left subtree, then the right subtree

5Return the assembled node

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
30
91
202
153
74
1 · Readpre[0]=3
2 · AskWhere is 3 in inorder?
3 · Update statemid=1; left span [0,0], right span [2,4]
4 · Resultcreate node 3; build left then right
Key takeaway

Preorder gives the root 3; inorder places 9 on its left and 15,20,7 on its right.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 12-13Precompute + pointer

    The index map gives O(1) splits; self.pre streams preorder roots in order.

  2. 2
    Lines 15-16Empty span

    When left exceeds right the subtree is empty, returning None.

  3. 3
    Lines 17-22Build root then recurse

    Take the next preorder value as root, split inorder at it, and construct left before right to match preorder's order.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Single-element arrays produce one leaf
  • Fully left- or right-skewed trees
  • Order matters: left must be built before right so the preorder pointer stays aligned
!

Common beginner mistakes

  • Building the right subtree before the left, which desynchronizes the preorder pointer
  • Re-scanning inorder with index() each call, degrading to O(n^2)
  • Off-by-one errors in the mid-1 / mid+1 boundaries
Check your understanding

Why must the left subtree be constructed before the right subtree?

More in Trees and Binary Search Trees

#104Maximum Depth of Binary TreePost-order height aggregation#543Diameter of Binary TreePost-order height with a running best#102Binary Tree Level Order TraversalLevel-by-level BFS#98Validate Binary Search TreeRange-bounded validation#236Lowest Common Ancestor of a Binary TreeBottom-up LCA search#124Binary Tree Maximum Path SumPost-order gain with global best