Construct Binary Tree from Preorder and Inorder Traversal
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.
Neither array alone determines the tree. Preorder gives us the root (it is always the first element) but not where the left subtree ends and the right subtree begins. In a BST the values themselves would tell us, but in a general binary tree they do not. Inorder supplies that boundary: once we know the root value, we can find it in the inorder array, and everything to its left belongs to the left subtree while everything to its right belongs to the right subtree.
Together the two arrays determine the structure completely: preorder identifies each root, and inorder splits the remaining values between its two subtrees.
Key Constraints:
1 <= preorder.length <= 3000→ With n up to 3000, an O(n^2) approach runs at most ~9 million operations, which passes. An O(n) solution exists using a hash map.- All values are unique → Each value appears at exactly one index in inorder, so the root's position, and therefore the split point, is unambiguous. With duplicate values, multiple trees could produce the same pair of traversals and reconstruction would not be well-defined.
Approach 1: Recursion with Linear Search
Intuition
The first element of preorder is the root of the whole tree. Finding that value in the inorder array splits inorder into two parts: the values before it are the left subtree's inorder sequence, and the values after it are the right subtree's inorder sequence.
That split also divides the rest of preorder. If the left subtree has k nodes (counted from the inorder split), the k elements after the root in preorder are the left subtree's preorder sequence, and the remaining elements are the right subtree's preorder sequence. This works because preorder visits the entire left subtree before any node of the right subtree, so the two groups occupy contiguous, non-overlapping ranges.
Each subtree now has its own preorder and inorder ranges, and the same logic applies to it: take the first preorder element as the root, find it in inorder, split, and recurse. An empty range is the base case and contributes no node.
Algorithm
- If the current range is empty, return null.
- Take the first element in the current preorder range as the root.
- Scan the inorder range to find the root's position.
- The number of elements before the root in inorder is the left subtree size.
- Recursively build the left subtree from the matching slices of preorder and inorder.
- Recursively build the right subtree from the remaining slices.
- Return the root with both children attached.
Example Walkthrough
Code
- Time Complexity: O(n^2) in the worst case. Each node is created once, but locating the root in the inorder range is a linear scan. For a left-skewed tree the root sits at the end of every range, so the scans cost n + (n-1) + ... + 1 = O(n^2) in total. For a balanced tree the total is O(n log n).
- Space Complexity: O(h) for the recursion stack, where h is the tree height (O(n) worst case for a skewed tree). No additional data structures are used.
The linear scan is the only part of each call that costs more than constant time. Precomputing every value's index in inorder removes it and brings the total time down to O(n).
Approach 2: Recursion with Hash Map
Intuition
Before the recursion starts, iterate through the inorder array once and map each value to its index. The values are unique, so each value has exactly one index and the map is well defined. Locating the root inside the current inorder range then becomes a single O(1) lookup, and each of the n recursive calls does constant work.
Nothing else changes: preorder still supplies each root, the map supplies the split point, and the recursion runs on both halves. The cost is the O(n) memory the map occupies.
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.
The hash map removes the scan but adds O(n) memory on top of the recursion stack. The map itself can also be removed: the boundary between subtrees can be detected from the inorder sequence as it is consumed.
Approach 3: Recursion with a Stop Value (Optimal)
Intuition
The hash map exists to answer one question: where does the left subtree end inside inorder? That boundary can also be detected without precomputing anything, by consuming both arrays left to right.
Keep two indices that are shared across all recursive calls. preIndex points at the next node to create; preorder order is exactly the order in which this construction creates nodes. inIndex points at the next inorder entry to consume. Instead of index ranges, each recursive call receives a stop value: the value that marks the end of its subtree in the inorder sequence.
For a node's left subtree, the stop value is the node's own value, because inorder visits the entire left subtree immediately before the node itself. The left recursion keeps creating nodes from preorder until inorder[inIndex] equals that value. The node then consumes its own inorder entry and builds its right subtree with the stop value it received from its caller: in inorder, the right subtree is followed by the same boundary that followed the node.
The comparison against the stop value is unambiguous only because all values are unique. If the stop value could also appear inside the subtree, the recursion would terminate at the wrong occurrence. The initial call passes a sentinel that cannot equal any node value, so the outermost recursion stops only when preorder is exhausted.
Algorithm
- Initialize
preIndex = 0andinIndex = 0, shared across all calls. - Start the recursion with a sentinel stop value that no node value can equal.
- In each call, return null if
preIndexhas reached the end of preorder orinorder[inIndex]equals the stop value. - Otherwise, create a node from
preorder[preIndex]and advancepreIndex. - Build the left subtree with the new node's value as the stop value.
- Advance
inIndexpast the node's own inorder entry. - Build the right subtree with the stop value the current call received, attach both children, and return the node.
Example Walkthrough
Code
- Time Complexity: O(n). preIndex and inIndex each advance exactly n times over the whole run, each call does constant work outside its recursive calls, and each node makes two calls, so there are O(n) calls in total.
- Space Complexity: O(h) for the recursion stack, where h is the tree height (O(n) worst case for a skewed tree). No hash map or other auxiliary structure is needed.