Reconstruct BST

Tags

Reconstruct BST

Category

Binary Search Trees (BST)

Difficulty

Medium

Problem Statement

Given a non-empty array of integers representing the pre-order traversal of a BST, reconstruct the BST and return its root node. The input array contains the values of the BST nodes in the order they were visited during a pre-order traversal (node, left, right). Each value in the array is unique.

Intuition

In a pre-order traversal, the first element is always the root. All subsequent elements that are less than the root belong to the left subtree, and all elements that are greater belong to the right subtree. This partitioning is unique because BST values are distinct and the BST property enforces strict ordering.

Rather than scanning to find the partition point each time (which leads to O(n^2)), we can use a range-based approach. Each recursive call maintains the valid range for the current subtree. We iterate through the array once, and each value naturally falls into the correct position in the tree.

Approach

  1. Maintain a global index pointer starting at 0.
  2. Recursively build the tree with lower and upper bounds: a. If the index is out of bounds or the current value violates the range [lower, upper], return null. b. Create a node with the current value and advance the index. c. Recursively build the left subtree with the updated upper bound (current value). d. Recursively build the right subtree with the updated lower bound (current value). e. Return the node.
  3. Start with bounds of (-infinity, +infinity).

Pseudocode

function reconstructBST(preOrderValues):
    index = { value: 0 }
    return buildTree(preOrderValues, index, -INFINITY, +INFINITY)

function buildTree(array, index, lowerBound, upperBound):
    if index.value >= length(array):
        return null
    currentValue = array[index.value]
    if currentValue < lowerBound or currentValue >= upperBound:
        return null
    index.value += 1
    node = new BSTNode(currentValue)
    node.left = buildTree(array, index, lowerBound, currentValue)
    node.right = buildTree(array, index, currentValue, upperBound)
    return node

Time & Space Complexity

  • Time: O(n), where n is the number of values. Each value is processed exactly once as the index advances monotonically.
  • Space: O(n) for the tree nodes. The call stack uses O(h) space where h is the height of the resulting tree (O(log n) for balanced, O(n) for skewed).

Key Insights

  • The range-based approach avoids the naive O(n^2) partition search by using bounds to determine when a subtree ends.
  • The index pointer is shared across all recursive calls and only moves forward, guaranteeing linear time.
  • Pre-order traversal uniquely defines a BST because the BST property constrains where each value can be placed.
  • This same technique applies to constructing a BST from a serialized format.

Edge Cases

  • Single element: return a tree with one node.
  • Sorted ascending array: produces a right-skewed BST (every node has only a right child).
  • Sorted descending array: produces a left-skewed BST (every node has only a left child).
  • Two elements: the second element is either the left or right child depending on its value relative to the root.

Linked mentions