← Back to DSA Animator
Construct Binary Tree from Preorder and Inorder LC #105 Medium DFS · Divide & Conquer
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.

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,2,3], inorder = [2,1,3]
Output: [1,2,3]
Constraints: 1 ≤ n ≤ 3000  |  preorder.length == inorder.length  |  All values unique
Try Examples
Custom:
Approach
DFS Divide & Conquer
preorder[preL] is always the current subtree root. Find it in inorder to split left / right subtrees. leftSize = inMid - inL maps to preorder offsets. Recurse both halves.
Binary Tree (Growing)
Select an example to begin…
Current Root
Placed
Processing
Default
Traversal Arrays
Waiting for input…
No active call yet
Recursion Call Stack
Stack is empty — not started
Variables
rootVal
—
preL..preR
—
inL..inR
—
leftSize
—
Step Logic
Press ▶ Play or Next Step to begin the animation.
🎉
Tree Built!
Algorithm Steps
1
preorder[preL] is always the root of the current subtree
2
Find root in inorder array → split left / right subtrees
3
leftSize = inMid - inL elements go to the left subtree
4
Recurse: build(left range) then build(right range)
Time
O(n)
Space
O(n)
Why It Works

preorder[0] is always the root. Finding it in inorder splits the array into left and right subtrees. The number of elements to the left (leftSize = inMid − inL) tells us exactly which portion of preorder belongs to the left subtree: pre[preL+1 .. preL+leftSize]. Everything after belongs to the right. A HashMap pre-indexes inorder values for O(1) lookup, giving overall O(n) time.