Construct Binary Tree from Preorder and Inorder Traversal
MediumGiven 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. The preorder traversal visits root, left subtree, then right subtree. The inorder traversal visits left subtree, root, then right subtree.
Examples
Example 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
Explanation: The root is 3 (first in preorder). In inorder, elements left of 3 ([9]) form the left subtree, and elements right of 3 ([15,20,7]) form the right subtree. Recursively, 9 is a leaf, and 20 becomes the right subtree root with 15 and 7 as children.
Example 2:
Input: preorder = [-1], inorder = [-1]
Output: [-1]
Explanation: A single element means the tree has only one node. The root is -1 with no children.
Constraints:
1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
All values in preorder and inorder are unique.
Algorithm Walkthrough
The most efficient approach to solve this problem uses a recursive divide-and-conquer strategy with a hashmap for O(1) lookups. The key insight lies in understanding what each traversal order reveals about the tree's structure. In a preorder traversal (root, left, right), the very first element is always the root of the tree (or subtree). In an inorder traversal (left, root, right), once you know the root value, everything to its left belongs to the left subtree and everything to its right belongs to the right subtree. This fundamental property allows us to recursively reconstruct the entire tree.
Let's walk through Example 1 step by step. Given preorder = [3, 9, 20, 15, 7] and inorder = [9, 3, 15, 20, 7]. The first element in preorder is 3, so 3 is our root. Scanning inorder for 3, we find it at index 1. This tells us that element at inorder[0] = 9 belongs to the left subtree (1 element), and elements at inorder[2..4] = [15, 20, 7] belong to the right subtree (3 elements).
Now we recurse. For the left subtree, we call array_to_tree(0, 0) since there's one element in the left portion. The next preorder element is 9, which becomes the left child. Its position in inorder is index 0, so left and right boundaries collapse and recursion returns None for both children. For the right subtree, we call array_to_tree(2, 4). The next preorder element is 20, found at inorder index 3. Elements inorder[2] = 15 go left, and inorder[4] = 7 goes right. Each of these is a leaf node with no further children.
A critical optimization is building a hashmap that maps each inorder value to its index before starting the recursion. This converts the O(n) linear scan for the root position in each recursive call into an O(1) hashmap lookup. Without this optimization, the algorithm would degrade to O(n²) because each of the n recursive calls would scan up to n elements.
Another important technique is using a preorder index pointer (a mutable counter or class member) instead of slicing the preorder array. Array slicing creates O(n) copies and complicates index tracking. By maintaining a single index that advances as we consume root values from preorder, we avoid all slicing overhead. The pointer naturally advances through preorder in the correct order because we always process the root first, then recursively build the left subtree (consuming all left subtree roots from preorder), and finally the right subtree (consuming all right subtree roots).
- Build a
hashmapmapping each inorder value to its index for O(1) lookups - Initialize a
preorder_idxpointer starting at 0 - Define a recursive function
array_to_tree(left, right)that builds the subtree from inorder[left..right] - If
left > right, return null (no subtree) - Read the current root from
preorder[preorder_idx], advance the pointer - Find root's position in inorder via the hashmap, split into left and right ranges, recurse
Idea Map
Build inorder_map = {val: idx}
Set preorder_idx = 0
Call array_to_tree(0, n-1)
If left > right return null
1. Root = preorder[preorder_idx++]
2. Find root index in inorder_map
3. root.left = recurse on left range
4. root.right = recurse on right range
Complexity Analysis
Time Complexity
O(n) - Each node is visited exactly once during the recursive construction. The hashmap provides O(1) lookup for finding the root's position in the inorder array, eliminating the need for linear scans. Building the hashmap itself is O(n), and there are exactly n recursive calls (one per node), each performing only constant-time work.
Space Complexity
O(n) - The hashmap storing inorder indices uses O(n) space. The recursion call stack can grow up to O(n) in the worst case for a completely skewed tree (where each recursive call processes a subtree of size n-1). For a balanced tree, the recursion depth is O(log n), but the hashmap dominates at O(n).
Code
def buildTree(preorder, inorder):
Defines the function `buildTree` which takes the preorder and inorder traversal arrays and returns the root of the reconstructed binary tree.
inorder_map = {val: i for i, val in enumerate(inorder)}
Build a hashmap mapping each value in inorder to its index. This gives O(1) lookup for finding the root's position instead of O(n) linear scan, which is the key optimization.
preorder_idx = 0
Initialize a pointer to track our current position in the preorder array. Using a pointer instead of slicing avoids O(n) array copy overhead at each recursive call.
def array_to_tree(left, right):
Defines the recursive helper function that constructs the subtree from inorder[left..right]. The `left` and `right` boundaries delimit the portion of inorder belonging to this subtree.
nonlocal preorder_idx
Declare `preorder_idx` as nonlocal so the nested function can modify it. Every recursive call shares and advances the same pointer through preorder.
if left > right:
Base case: if the left boundary exceeds the right boundary, this subtree is empty — return None.
return None
Return None to signal that there is no node at this position in the tree.
root_val = preorder[preorder_idx]
Read the current root value from preorder. In preorder (root-left-right), the next unconsumed element is always the root of the current subtree.
root = TreeNode(root_val)
Create a new TreeNode with the root value. This node will be connected to its left and right subtrees in the next steps.
preorder_idx += 1
Advance the preorder pointer. After consuming the root, the next elements in preorder are the roots of the left subtree, followed by the right subtree.
root.left = array_to_tree(left, inorder_map[root_val] - 1)
Recursively build the left subtree. The left portion of inorder (from `left` to one position before the root) contains all nodes in the left subtree. Must recurse left first since preorder processes left before right.
root.right = array_to_tree(inorder_map[root_val] + 1, right)
Recursively build the right subtree. The right portion of inorder (from one position after the root to `right`) contains all nodes in the right subtree. This runs after the left subtree is fully built.
return root
Return the constructed subtree rooted at this node. Each call returns a fully formed subtree.
return array_to_tree(0, len(preorder) - 1)
Kick off the recursion with the full range of inorder indices [0, n-1]. This constructs the entire tree and returns the root node.
class Solution {
Defines the Solution class. We use instance variables to share state across recursive calls without passing them through every method parameter.
int preorderIndex;
Instance variable tracking the current position in the preorder array. Shared across all recursive calls — advances as roots are consumed.
Map<Integer, Integer> inorderIndexMap;
HashMap mapping each inorder value to its index. Provides O(1) lookups during recursion, avoiding O(n) linear scans for the root position.
int[] preorder;
Store the preorder array as an instance variable so the recursive helper can access it without passing it as a parameter each time.
int[] inorder;
Store the inorder array as an instance variable for the same reason — shared access across all recursive calls.
public TreeNode buildTree(int[] preorder, int[] inorder) {
Public entry point that takes preorder and inorder arrays and returns the root of the reconstructed binary tree.
this.preorder = preorder;
Store the preorder array reference in the instance variable for access by the recursive helper method.
this.inorder = inorder;
Store the inorder array reference in the instance variable for access by the recursive helper method.
preorderIndex = 0;
Initialize the preorder pointer to 0. It will advance as we consume root values from the preorder array during recursion.
inorderIndexMap = new HashMap<>();
Create a new HashMap to store the inorder value-to-index mapping.
for (int i = 0; i < inorder.length; i++) {
Iterate through the inorder array to populate the hashmap with each value and its corresponding index.
inorderIndexMap.put(inorder[i], i);
Map each inorder value to its index. This O(n) preprocessing enables O(1) root lookups during the recursive tree construction phase.
}
End of the hashmap building loop.
return arrayToTree(0, inorder.length - 1);
Start the recursive construction with the full inorder range [0, n-1]. Returns the root of the fully reconstructed tree.
}
End of the buildTree method.
private TreeNode arrayToTree(int left, int right) {
Private recursive helper that constructs the subtree from inorder[left..right]. Uses instance variables for preorder access and the index pointer.
if (left > right) return null;
Base case: if the range is invalid (left exceeds right), this subtree is empty — return null.
int rootValue = preorder[preorderIndex++];
Read the current root value from preorder and immediately advance the pointer (post-increment). In preorder, the next unconsumed element is always the current subtree's root.
TreeNode root = new TreeNode(rootValue);
Create a new TreeNode with the root value. This node will be the root of the subtree being constructed.
root.left = arrayToTree(left, inorderIndexMap.get(rootValue) - 1);
Recursively build the left subtree using the portion of inorder left of the root. Must recurse left first since preorder processes left subtree before right.
root.right = arrayToTree(inorderIndexMap.get(rootValue) + 1, right);
Recursively build the right subtree using the portion of inorder right of the root. The preorder pointer now points to the first right-subtree element.
return root;
Return the fully constructed subtree rooted at this node.
}
End of the arrayToTree helper method.
}
End of the Solution class.
class Solution {
Defines the Solution class. Uses member variables to share state (preorder index and inorder map) across recursive calls without extra parameters.
int preorderIndex;
Member variable tracking the current position in the preorder vector. Shared across all recursive calls and advanced as root values are consumed.
unordered_map<int, int> inorderIndexMap;
Hashmap mapping each inorder value to its index. `unordered_map` provides O(1) average-case lookup, enabling fast root position finding during recursion.
TreeNode* arrayToTree(vector<int>& preorder, int left, int right) {
Private recursive helper that constructs the subtree from inorder[left..right]. Takes a reference to preorder to read root values using the shared index pointer.
if (left > right) return nullptr;
Base case: if the range is invalid (left exceeds right), this subtree is empty — return nullptr. This also handles leaf nodes whose children are null.
int rootValue = preorder[preorderIndex++];
Read the root value from preorder using the current index and advance the pointer. Post-increment ensures the next call gets the next root value in preorder order.
TreeNode* root = new TreeNode(rootValue);
Allocate a new TreeNode on the heap with the root value. This node will serve as the root of the current subtree being constructed.
root->left = arrayToTree(preorder, left, inorderIndexMap[rootValue] - 1);
Recursively build the left subtree. The left portion of inorder (from `left` to root index - 1) contains all left subtree nodes. Must recurse left first since preorder processes left before right.
root->right = arrayToTree(preorder, inorderIndexMap[rootValue] + 1, right);
Recursively build the right subtree. The right portion of inorder (from root index + 1 to `right`) contains all right subtree nodes. Runs after the left subtree is fully built.
return root;
Return the fully constructed subtree rooted at this node. The caller (parent recursion or main method) receives the completed subtree.
}
End of the arrayToTree private helper method.
public:
Public access specifier for the LeetCode-required entry point method.
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
Public entry point that takes references to preorder and inorder vectors and returns a pointer to the reconstructed tree's root.
preorderIndex = 0;
Initialize the preorder index pointer to 0. It starts at the beginning and advances as root values are consumed during recursive construction.
for (int i = 0; i < inorder.size(); i++) {
Iterate through the inorder vector to populate the hashmap with each value and its corresponding index.
inorderIndexMap[inorder[i]] = i;
Map each inorder value to its index in the array. This O(n) preprocessing step enables O(1) root position lookups during recursion.
}
End of the hashmap building loop.
return arrayToTree(preorder, 0, inorder.size() - 1);
Start the recursive construction with the full inorder range [0, n-1]. Returns the root of the fully reconstructed binary tree.
}
End of the buildTree method.
};
End of the Solution class.
Edge Cases & Common Mistakes
Duplicate values break the hashmap approach
This algorithm relies on the guarantee that all values in the preorder and inorder arrays are unique. If duplicate values exist, the hashmap maps multiple positions to the same key, and you cannot reliably determine which occurrence of a value corresponds to the root at the current recursion level. The problem constraints specify unique values, but be aware of this limitation if adapting the solution.
Use a preorder index pointer instead of array slicing
A common mistake is to slice the preorder array at each recursive call (e.g., `preorder[1:left_size+1]` for the left subtree). Array slicing creates a new copy in O(n) time and space per call, degrading the overall complexity to O(n²). Instead, maintain a single preorder index that advances as roots are consumed. The recursion order (left before right) naturally ensures the pointer reads values in the correct sequence.
Hashmap for inorder index lookups is the key optimization
Without the hashmap, finding the root's position in the inorder array requires a linear scan (O(n) per call), making the total time complexity O(n²). The hashmap reduces each lookup to O(1), bringing the overall complexity to O(n). Always build the hashmap before starting recursion. This single optimization transforms the solution from acceptable to optimal.
Related Problems
Understanding Tree Construction
Tree construction from traversal arrays is a fundamental technique that deepens your understanding of how different traversal orders encode tree structure. Mastering this pattern unlocks the ability to reconstruct trees from any combination of traversal orders and strengthens your recursive problem-solving skills.
Learn more about understanding tree construction →Disclaimer: This problem is for educational purposes. Practice the 'Construct Binary Tree from Preorder and Inorder Traversal' problem on LeetCode.