DSA AnimatorDSA animations
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.

How to solve Construct Binary Tree from Preorder and Inorder Traversal

LeetCode 105 · Medium · Tree · Pattern: Divide and Conquer

Why the obvious approach is slow

Trying every possible tree shape and checking both traversals is hopeless. The two traversals carry complementary information, and together they fix the tree.

The key idea

The first value of the preorder is always the root. Find that root in the inorder, and everything to its left belongs to the left subtree. Everything to its right belongs to the right subtree. The size of the left part tells you how many preorder values belong to the left subtree. Use a hash map from value to inorder index, so each lookup is O(1).

Remember

Preorder gives the root, inorder gives the split. Build left before right, so the preorder pointer stays in sync.

Run the animation above on your own input, or watch the 2:16 video explanation of Construct Binary Tree from Preorder and Inorder Traversal with a dry run and Java code.

More Tree problems