LeetCode 1008: Construct Binary Search Tree from Preorder Traversal

Problem Restatement

We are given the preorder traversal of a binary search tree (BST) in an array preorder.

We need to reconstruct the BST and return its root.

Recall that in a BST, for every node, all values in the left subtree are smaller, and all values in the right subtree are larger.

In preorder traversal, we visit the root before the left and right subtrees.

The official constraints state that 1 <= preorder.length <= 100, all values in preorder are distinct, and it is guaranteed that the input represents a valid BST.

Input and Output

Function shape:

def bstFromPreorder(preorder: list[int]) -> Optional[TreeNode]:
    ...

Examples

Example 1:

preorder = [8, 5, 1, 7, 10, 12]

Root is 8. Left subtree has values [5, 1, 7] (all less than 8). Right subtree has values [10, 12] (all greater than 8).

The BST:

      8
     / \
    5   10
   / \    \
  1   7   12

Key Insight

In preorder traversal, the first element is always the root.

All subsequent elements less than the root belong to the left subtree.

All subsequent elements greater than the root belong to the right subtree.

We can find the split point and recursively build left and right subtrees.

Alternatively, use a range-based recursive approach with an index pointer:

• The root is preorder[index].
• The left subtree takes values less than the upper bound.
• The right subtree takes values greater than the lower bound.

Algorithm

Use a recursive function with a global index and value bounds:

1. If the index is out of bounds or the current value is out of the [lower, upper) range, return None.
2. Create a node with the current value.
3. Advance the index.
4. Recursively build the left child with upper bound set to the current node’s value.
5. Recursively build the right child with lower bound set to the current node’s value.
6. Return the node.

Correctness

The BST property guarantees that all values for the left subtree fall in (lower, root.val) and all values for the right subtree fall in (root.val, upper).

Preorder traversal visits root, then left subtree, then right subtree. So consuming elements in preorder with the correct bounds produces exactly the right subtree structure.

Edge Cases

• A missing child should not contribute a fake value to min/max or path computations.
• Leaf nodes often define the base case; verify the behavior on a single-node tree.
• When passing state down the tree, update it before visiting children that depend on the current node.

Complexity

Common Pitfalls

• Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
• Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

from typing import Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def bstFromPreorder(self, preorder: list[int]) -> Optional[TreeNode]:
        self.idx = 0

        def build(lower: float, upper: float) -> Optional[TreeNode]:
            if self.idx == len(preorder):
                return None
            val = preorder[self.idx]
            if val < lower or val > upper:
                return None

            node = TreeNode(val)
            self.idx += 1
            node.left = build(lower, val)
            node.right = build(val, upper)
            return node

        return build(float("-inf"), float("inf"))

Code Explanation

We maintain a shared index pointing to the current preorder element:

self.idx = 0

The recursive function checks whether the current value fits within the allowed range:

val = preorder[self.idx]
if val < lower or val > upper:
    return None

If valid, create the node and advance the index:

node = TreeNode(val)
self.idx += 1

Recursively build left and right subtrees with updated bounds:

node.left = build(lower, val)
node.right = build(val, upper)

Alternative: Split by Index

We can also find where the right subtree starts using binary search on the preorder array.

class Solution:
    def bstFromPreorder(self, preorder: list[int]) -> Optional[TreeNode]:
        if not preorder:
            return None
        root = TreeNode(preorder[0])
        mid = len(preorder)
        for i in range(1, len(preorder)):
            if preorder[i] > preorder[0]:
                mid = i
                break
        root.left = self.bstFromPreorder(preorder[1:mid])
        root.right = self.bstFromPreorder(preorder[mid:])
        return root

This approach is simpler but creates subarrays, making it O(n^2) in the worst case.

Testing

def preorder_list(root):
    if not root:
        return []
    return [root.val] + preorder_list(root.left) + preorder_list(root.right)

def run_tests():
    s = Solution()

    root = s.bstFromPreorder([8, 5, 1, 7, 10, 12])
    assert preorder_list(root) == [8, 5, 1, 7, 10, 12]

    root = s.bstFromPreorder([1, 3])
    assert preorder_list(root) == [1, 3]

    root = s.bstFromPreorder([5])
    assert preorder_list(root) == [5]

    print("all tests passed")

run_tests()