Construct Binary Search Tree from Preorder Traversal
Understanding the Problem
We're given an array that represents the preorder traversal of a BST, and we need to reconstruct the original tree. Preorder visits the root first, then the left subtree, then the right subtree, so the first element of the array is always the root.
The BST property determines everything else. All values smaller than the root belong to the left subtree, and all values larger belong to the right subtree. Because preorder lists the entire left subtree before the right subtree, the array for any subtree has the shape [root, left subtree values, right subtree values]. The first element greater than the root marks where the right subtree begins, and the same structure repeats inside each half.
Key Constraints:
1 <= preorder.length <= 100→ With n up to 100, even an O(n^2) approach passes. There is room for brute force, but O(n) is achievable.1 <= preorder[i] <= 1000→ Values fit comfortably in 32-bit integers, so the maximum integer value can serve as a sentinel upper bound.- All values are unique → Every comparison is strict. Each element is either less than or greater than the root, so the split between left and right subtree is unambiguous.
Approach 1: Recursive with Linear Search for Split Point
Intuition
The array structure from the problem analysis translates directly into a recursive algorithm. Take the first element of the current range as the root, scan forward for the first element greater than it, and split the rest there: everything before the split is the left subtree's preorder, everything from the split onward is the right subtree's preorder. Build each side the same way.
Algorithm
- If the array is empty, return null.
- Take the first element as the root of the current subtree.
- Find the index of the first element greater than the root. This is the split point.
- Everything from index 1 to the split point forms the left subtree's preorder.
- Everything from the split point to the end forms the right subtree's preorder.
- Recursively build the left and right subtrees.
Example Walkthrough
Code
- Time Complexity: O(n^2) in the worst case. For each node, we scan through the remaining elements to find the split point. In a skewed tree, each call scans nearly the entire remaining array: O(n) + O(n-1) + ... + O(1) = O(n^2). For a balanced BST, this is O(n log n).
- Space Complexity: O(h) for the recursion stack, where h is the height of the tree (O(n) worst case for a skewed tree, O(log n) for a balanced one).
The linear scan for the split point is the bottleneck. The next approach replaces it with a binary search.
Approach 2: Recursive with Binary Search for Split Point
Intuition
The idea is the same as Approach 1: take the first element as the root, split the rest into left and right subtree portions, and recurse. The difference is how we find the split point.
Within any subtree's range, all left-subtree elements are less than the root and all right-subtree elements are greater, so the range after the root is a block of smaller values followed by a block of larger values. That monotone less-than/greater-than transition is a valid target for binary search: find the first element that exceeds the root value. This reduces the split-point search from O(n) to O(log n).
Algorithm
- If the subarray is empty, return null.
- Take the first element as the root.
- Binary search in the range [start + 1, end] for the first index where the value exceeds the root's value.
- Recursively build the left subtree from [start + 1, splitIndex - 1].
- Recursively build the right subtree from [splitIndex, end].
Example Walkthrough
Code
- Time Complexity: O(n log n) in the worst case. A skewed tree forces n recursive calls, each paying O(log n) for its binary search. For a balanced tree, the recurrence T(n) = 2T(n/2) + O(log n) resolves to O(n), because the O(log n) search cost per call is dominated by the number of calls at the lower levels of the recursion.
- Space Complexity: O(h) for the recursion stack, where h is the height of the tree (O(n) worst case for a skewed tree).
Both approaches so far spend time locating split points. The next approach removes that search entirely: it processes the preorder array left to right and uses value bounds to decide where each element belongs.
Approach 3: Recursive with Upper Bound
Intuition
Instead of finding split points, we process the preorder array left to right using a single index, and we pass an upper bound to each recursive call: the maximum value a node in that subtree is allowed to have.
When we recurse into the left subtree of a node with value 8, the upper bound becomes 8, since all left-subtree values must be less than 8. When we recurse into the right subtree, the upper bound stays whatever the parent received, because the constraint from higher up the tree still applies.
At each step, we compare the current element against the bound. If it is less than the bound, it belongs in the current subtree: create a node and advance the index. If it exceeds the bound, the current subtree is complete: return null without consuming the element, and a caller higher up the recursion will place it. Each element is consumed exactly once, so construction takes O(n).
At any moment during construction, several subtrees are open (started but not finished), and their upper bounds are nested: each left-subtree bound is tighter than every bound above it. The next array element x is tested against the innermost bound first. If x is below that bound, x must belong to the innermost open subtree, because preorder lists every node of a subtree before any node that follows the subtree. If x exceeds the bound, the innermost subtree cannot contain x (all of its values lie below the bound), so that subtree is finished, the call returns, and x is retested against the next enclosing bound. Each element is therefore placed in the deepest open subtree that can legally contain it, which is the position preorder dictates.
Algorithm
- Initialize a global index at 0 to track our position in the preorder array.
- Call a recursive helper with an upper bound of infinity (Integer.MAX_VALUE).
- In the helper:
- If the index is out of bounds or the current value exceeds the upper bound, return null.
- Create a node with the current value and advance the index.
- Recursively build the left child with the current node's value as the upper bound.
- Recursively build the right child with the original upper bound passed to this call.
- Return the node.
Visualization and Code
Loading animation...
- Time Complexity: O(n). Each element in the preorder array is visited exactly once. We advance the index by 1 for each node we create, and the total number of nodes equals n.
- Space Complexity: O(h) for the recursion stack, where h is the height of the tree (O(n) worst case for a skewed tree, O(log n) for a balanced one).
The recursion in Approach 3 tracks open subtrees on the call stack. An explicit stack does the same bookkeeping iteratively, in the same O(n) time.
Approach 4: Iterative with Monotonic Stack
Intuition
Maintain a stack of nodes that are still waiting for a right child. Values on the stack strictly decrease from bottom to top: a new node is pushed either as the left child of the current top, so it is smaller, or after the pop loop has stopped at a node with a larger value. The top of the stack is always the most recently processed element. For each new value v from the array:
- If v is smaller than the value on top of the stack, v is the left child of the top node. In preorder, the element immediately after a node is the root of its left subtree whenever that subtree is non-empty, and v being smaller confirms it is.
- Otherwise, pop nodes while the top of the stack is smaller than v, remembering the last node popped. Every popped node has a value below v, so v lies in its right subtree. The last node popped is the deepest of them, so v attaches as its right child.
Either way, push the new node, since it may still receive a right child later. Each node is pushed once and popped at most once, so the whole construction is O(n) with no recursion.
Algorithm
- Create the root from the first element and push it onto the stack.
- For each remaining value v:
- Create a node for v.
- If v is less than the value on top of the stack, attach the node as the left child of the top node.
- Otherwise, pop while the stack is non-empty and the top value is less than v, keeping a reference to the last node popped. Attach the new node as that node's right child.
- Push the new node.
- Return the root.
Example Walkthrough
Code
- Time Complexity: O(n). Each node is pushed exactly once and popped at most once, so the total work across all iterations is linear.
- Space Complexity: O(h) for the explicit stack, where h is the height of the tree (O(n) worst case for a skewed tree). The stack holds the chain of nodes still waiting for a right child, which is at most one path from the root.