Construct Binary Tree from Preorder and Inorder Traversal
Last Updated: April 1, 2026
Understanding the Problem
We have two arrays that describe the same binary tree from different perspectives. Preorder traversal visits root, then left subtree, then right subtree. Inorder traversal visits left subtree, then root, then right subtree.
The question is: can we combine these two perspectives to uniquely reconstruct the original tree? The answer is yes, and the reasoning is elegant.
The preorder array always tells us the root first. But preorder alone cannot tell us where the left subtree ends and the right subtree begins (unlike a BST where values give us that split). That is where inorder comes in. Once we know the root, we can find it in the inorder array, and everything to its left in inorder belongs to the left subtree, everything to its right belongs to the right subtree. This gives us the split point we need.
So the two traversals complement each other perfectly: preorder identifies the root, and inorder tells us the subtree boundaries.
Key Constraints:
1 <= preorder.length <= 3000→ With n up to 3000, an O(n^2) approach runs at most ~9 million operations, which is fine. But we can do O(n) with a hash map optimization.-3000 <= preorder[i], inorder[i] <= 3000→ Values can be negative. No impact on the algorithm, but good to note.- All values are unique → This is crucial. It means we can locate any value in the inorder array unambiguously. Without uniqueness, the problem would be ambiguous.
Approach 1: Recursion with Linear Search
Intuition
The most natural approach comes from understanding what each traversal tells us.
Preorder gives us the root immediately, it is always the first element. But it does not tell us where the left subtree ends and the right subtree begins. In a BST, the values themselves tell us this (everything smaller goes left), but in a general binary tree, we cannot rely on that.
This is where inorder comes in. Once we know the root value from preorder, we can find it in the inorder array. Everything to the left of the root's position in inorder belongs to the left subtree, and everything to the right belongs to the right subtree. This is exactly by definition of inorder traversal: left, root, right.
Here is the really useful part: once we know the left subtree has, say, k nodes (from the inorder split), we also know the next k elements in the preorder array after the root form the left subtree's preorder. The remaining elements form the right subtree's preorder.
So we recursively apply the same logic: pick the root from preorder, find it in inorder to get the split, and recurse on both halves.
Algorithm
- If the current range is empty (no elements to process), return null.
- Take the first element in the current preorder range as the root.
- Scan the inorder array to find this root's position.
- The number of elements to the left of the root in inorder gives us the left subtree size.
- Recursively build the left subtree using the appropriate slices of preorder and inorder.
- Recursively build the right subtree using the remaining slices.
- Return the root with its left and right children attached.
Example Walkthrough
Code
- Time Complexity: O(n^2). We process each node once, but finding the root in the inorder array takes O(n) in the worst case (linear scan). For a skewed tree, every recursive call scans nearly the entire remaining inorder array, giving O(n) work across n levels.
- Space Complexity: O(n). The recursion stack can go as deep as n for a completely skewed tree. No additional data structures are used.
This approach works correctly, but for every node we create, we scan the inorder array to find the root's position. What if we pre-computed every value's position so lookups were O(1)?
Approach 2: Recursion with Hash Map (Optimal)
Intuition
The algorithm from Approach 1 is fundamentally correct. The only thing slowing it down is the linear search to find the root in the inorder array. If we could look up any value's index in O(1), each recursive call would do O(1) work, and the total time would drop to O(n).
A hash map is the perfect tool for this. Before we start building the tree, we iterate through the inorder array once and map each value to its index. Then during recursion, finding the root's position in inorder becomes a single hash map lookup instead of a scan.
Everything else stays the same: preorder tells us the root, inorder (via the hash map) tells us the split, and we recurse on both halves.
The key insight is that preorder and inorder traversals encode complementary information. Preorder always reveals the root first, while inorder reveals the boundary between left and right subtrees. Together, they uniquely determine the tree structure.
The hash map does not change the algorithm at all, it just replaces the O(n) linear search with an O(1) lookup. Since we build the map once in O(n) and each of the n recursive calls does O(1) work, the total time is O(n).
Algorithm
- Build a hash map mapping each value in inorder to its index.
- Start the recursive build with the full range of both arrays.
- At each step, take the first element in the current preorder range as the root.
- Look up the root's index in the inorder array using the hash map (O(1)).
- Calculate the left subtree size from the inorder split.
- Recursively build the left subtree, then the right subtree.
- Return the constructed root.
Example Walkthrough
Code
- Time Complexity: O(n). Building the hash map takes O(n). Each of the n nodes is visited exactly once during recursion, and each visit does O(1) work (hash map lookup + node creation).
- Space Complexity: O(n). The hash map stores n entries. The recursion stack can go as deep as n for a skewed tree.