Description
You are given two arrays:
preorder– the preorder traversal of a binary tree.inorder– the inorder traversal of the same tree.
Both arrays contain unique values.
Your task is to reconstruct the original binary tree and return its root.
Example
preorder = [1,2,3,4]
inorder = [2,1,3,4]
Output:
1
/ \
2 3
\
4Key Observation
This problem looks intimidating at first because you're given two traversals instead of the tree itself.
The trick is understanding what information each traversal gives you.
Preorder Traversal
Preorder always visits nodes in this order:
Root
Left
RightSo the first element is always the root of the current subtree.
For example:
preorder = [3,9,20,15,7]Immediately tells us:
Root = 3Inorder Traversal
Inorder visits nodes as:
Left
Root
RightSo once we know the root, we can split the tree into two halves.
Example:
inorder = [9,3,15,20,7]Since 3 is the root:
Left subtree = [9]
Root = 3
Right subtree = [15,20,7]This single split tells us exactly which nodes belong on the left and right.
Solution 1 — Slice the Arrays
This is the most intuitive solution.
class Solution:
def buildTree(self, preorder, inorder):
if not preorder or not inorder:
return None
root = TreeNode(preorder[0])
mid = inorder.index(preorder[0])
root.left = self.buildTree(
preorder[1:mid+1],
inorder[:mid]
)
root.right = self.buildTree(
preorder[mid+1:],
inorder[mid+1:]
)
return rootStep-by-step Example
Suppose
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]Step 1
Root is always:
3Find it inside inorder.
[9, 3, 15,20,7]
^Everything left belongs to the left subtree.
Everything right belongs to the right subtree.
Left subtree
Inorder
[9]One node means preorder must also contain one node.
preorder[1:2]
↓
[9]Right subtree
Remaining preorder values belong to the right subtree.
[20,15,7]Corresponding inorder:
[15,20,7]Then recursion repeats exactly the same process.
Why does preorder[1:mid+1] work?
This is one of the trickiest parts.
Suppose
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]We found
mid = 1because 3 is at index 1.
The inorder left subtree contains
[9]which has
mid = 1element.
Since preorder starts with the root,
[3 | 9 | 20 15 7]the next one value must belong to the left subtree.
So
preorder[1:mid+1]becomes
preorder[1:2]
↓
[9]The size of the left subtree is determined entirely by the inorder traversal.
Complexity of Solution 1
Every recursive call does
inorder.index(...)which costs
O(n)It also creates sliced arrays.
Overall complexity becomes
Time: O(n²)
Space: O(n²)Although this passes, it isn't the optimal interview solution.
Solution 2 — Hash Map + Indices
Instead of slicing arrays repeatedly, we keep the original arrays and only track the current subtree boundaries.
class Solution:
def buildTree(self, preorder, inorder):
inorderIndex = {
val: i
for i, val in enumerate(inorder)
}
preorderIndex = 0
def dfs(left, right):
nonlocal preorderIndex
if left > right:
return None
node = TreeNode(preorder[preorderIndex])
mid = inorderIndex[preorder[preorderIndex]]
preorderIndex += 1
node.left = dfs(left, mid - 1)
node.right = dfs(mid + 1, right)
return node
return dfs(0, len(inorder)-1)Why use left and right?
Instead of creating new arrays like
inorder[:mid]and
inorder[mid+1:]we simply remember which portion of the inorder array belongs to this subtree.
For example
inorder
[9,3,15,20,7]Initially
left = 0
right = 4meaning
Entire arrayAfter finding root 3
the recursive calls become
Left subtree
left = 0
right = 0
↓
[9]and
Right subtree
left = 2
right = 4
↓
[15,20,7]No arrays are copied.
We're only changing the boundaries.
Why is the base case left > right?
Eventually recursion reaches an empty subtree.
Example
left = 2
right = 1There are no elements between those indices.
That means
No node exists here.So we return
NoneThis becomes the missing child of the parent node.
Why doesn't preorderIndex need to move differently?
Notice something interesting.
Every recursive call creates exactly one node.
Every node appears exactly once in preorder.
Therefore each time we build a node,
preorderIndex += 1is always correct.
It never needs to jump by more than one.
The recursion itself determines whether the next preorder value belongs to the left subtree or the right subtree.
Why doesn't inorderIndex need nonlocal?
We write
nonlocal preorderIndexbecause we're modifying it.
preorderIndex += 1changes the variable.
But
inorderIndexis only being read.
mid = inorderIndex[value]Reading outer variables doesn't require nonlocal.
Only reassignment does.
Complexity
Solution 1
Time
O(n²)index()is O(n)- Array slicing copies elements
Space
O(n²)because many sliced arrays are created.
Solution 2
Creating the hashmap:
O(n)Each node is processed exactly once.
Hash map lookup:
O(1)Overall:
Time
O(n)Space
O(n)- Hash map
- Recursive call stack
Interview Tips
There are two approaches worth knowing.
Approach 1
Use array slicing.
Pros:
- Very intuitive
- Easy to explain
- Great for understanding the recursion
Cons:
index()is O(n)- Array slicing creates many copies
- Overall O(n²)
Approach 2
Use:
- an inorder hashmap
- a global preorder index
- inorder boundaries (
left,right)
This avoids slicing entirely and achieves the optimal:
- Time: O(n)
- Space: O(n)
This is the solution interviewers usually expect for this problem.
Final Takeaways
- Preorder always tells you the next root.
- Inorder tells you where to split into left and right subtrees.
- The size of the left subtree comes from the inorder traversal.
- The preorder index always increments by exactly one because every recursive call creates exactly one node.
- Using
leftandrightboundaries avoids creating new arrays and reduces the complexity from O(n²) to O(n).
