Problem Breakdown
Restatement: We are given an array representing the Preorder traversal of a Binary Search Tree (BST). Our goal is to reconstruct that specific BST structure. In a preorder sequence [Root, Left..., Right...], the first element is always the root of the current subtree. All subsequent elements smaller than this root belong to its left child’s subtree, and all larger values eventually form the right side or ancestors’ right paths.
Inputs:
preorder: A list of unique integers representing node values in preorder sequence.
Outputs:
- The root node (
TreeNode) of the constructed BST.
Implicit Constraints & Edge Cases:
- BST Property: Strict inequality is required (Left < Node.val, Right > Node.val). No duplicates allowed per constraints and problem definition.
- Empty Input: Constraint guarantees
preorder.length >= 1, so we don’t need to handle empty lists explicitly in the logic, but a robust solution should returnNoneif bounds are violated (which implies end of tree construction for that branch). - Skewed Trees: If input is sorted ascending
[1,2,3], it forms a right-skewed line. If descending[3,2,1], left-skewed. The logic must handle depth without stack overflow (though Python recursion limit usually handles ~1000 frames). - Values: Integers up to . No overflow issues in standard languages; Python handles arbitrary precision integers automatically.
Intuition
Brute Force Approach: A naive solution might try to construct the tree by iterating through the remaining array for every node to find where the left subtree ends and right begins (finding the first value greater than current root). This requires scanning elements for each of the nodes, resulting in Time Complexity: .
Key Insight:
In a BST preorder traversal [Root] [Left Subtree < Root] [Right Subtree > Root], once we encounter a value larger than Root during recursion, it cannot belong to the left subtree of any ancestor above us. It must be part of an existing right path or become a new node on that path.
Optimal Approach:
We can use Recursion with Bounds. As we traverse the preorder array sequentially (using an index pointer), every node val is valid only if it falls within (min_val, max_val) constraints passed down from its ancestors. If val < current_node, it goes to the left child; otherwise (val > current_node), it belongs in a right subtree context or becomes a new root for that branch (effectively popping up). This ensures we visit each element exactly once.
Approach
- Initialize an index pointer at position
0. We need this as mutable state since Python passes integers by value, so wrapping the index in a list[0]is idiomatic to track progress across recursive calls without global variables. - Define a helper function
build(min_val, max_val):- Check if the current element at our pointer fits within
(min_val, max_val). If not (i.e., we’ve exhausted valid nodes for this branch), returnNoneto stop recursion down that path. - Create a new node with
preorder[index], then increment index. - Recursively build the left child: Pass
(min_val, current_node.val)as bounds (values must be smaller). - Recursively build the right child: Pass
(current_node.val, max_val)as bounds (values must be larger).
- Check if the current element at our pointer fits within
- Call
buildwith initial infinite bounds (-inf,+inf) to allow any valid integer in the tree.
Complexity Analysis
- Time Complexity: . We iterate through each element of
preorderexactly once via the index pointer. Each node is created and processed a constant number of times during recursion. - Space Complexity: , where is the height of the tree (due to call stack). In the worst case (skewed BST), this degrades to . Best case (balanced) is .
Solution
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
# Using a mutable list to track the current index in preorder array across recursive calls.
idx = 0
def bstFromPreorder(self, preorder):
if not preorder or len(preorder) == 0:
return None
# Helper function that constructs nodes within valid value bounds (min_val, max_val).
def build(min_v, max_v):
nonlocal idx
# If current index is out of range or value violates BST property relative to ancestors.
if self.idx >= len(preorder) or preorder[self.idx] < min_v:
return None
# Create node with valid value within bounds
val = preorder[self.idx]
self.idx += 1
root = TreeNode(val)
# Left child must be smaller than current node (and original lower bound)
root.left = build(min_v, val)
# Right child must be larger than current node but within upper ancestor bounds
root.right = build(val, max_v)
return root
# Initial call with infinite bounds to accept any valid integer in the tree.
self.idx = 0
return build(float('-inf'), float('inf'))
Edge Cases Handled
- Single Node: If
preorderhas one element, recursion builds it and immediately returns for children (bounds violation or index out of bounds). - Skewed Trees: The logic naturally handles strictly increasing or decreasing sequences by adjusting the
(min_v, max_v)window appropriately at each step. - Index Tracking: Using
nonlocal idxensures we don’t re-scan the array; once a value is consumed for a node (or skipped via bounds check), it’s never revisited in that branch path.