Domain 2MediumMEDIUM

Construct Binary Search Tree from Preorder Traversal

LeetCode problem 1008: Construct Binary Search Tree from Preorder Traversal (medium).

Domain: medium•Updated: 2026-09-06
#Tree

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:

  1. BST Property: Strict inequality is required (Left < Node.val, Right > Node.val). No duplicates allowed per constraints and problem definition.
  2. 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 return None if bounds are violated (which implies end of tree construction for that branch).
  3. 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 O(N)O(N) depth without stack overflow (though Python recursion limit usually handles ~1000 frames).
  4. Values: Integers up to 10810^8. 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 O(N)O(N) elements for each of the NN nodes, resulting in Time Complexity: O(N2)O(N^2).

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

  1. 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.
  2. 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), return None to 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).
  3. Call build with initial infinite bounds (-inf, +inf) to allow any valid integer in the tree.

Complexity Analysis

  • Time Complexity: O(N)O(N). We iterate through each element of preorder exactly once via the index pointer. Each node is created and processed a constant number of times during recursion.
  • Space Complexity: O(H)O(H), where HH is the height of the tree (due to call stack). In the worst case (skewed BST), this degrades to O(N)O(N). Best case (balanced) is O(log⁡N)O(\log N).

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 preorder has 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 idx ensures 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.