BST Iterator, Range Queries, and Closest Value

The BST iterator is one of the most elegant tree problems — it asks you to simulate an in-order traversal lazily, one element at a time. Combined with range queries and closest-value problems, these form a family of BST-specific techniques that exploit the sorted structure of a BST.

---

TreeNode Definition

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

---

Problem 1: BST Iterator (LeetCode 173)

Implement an iterator over a BST that returns elements in ascending order (in-order). The iterator should support:

• next() — return the next smallest element
• hasNext() — return whether there are more elements

The naive approach

Flatten the BST into a sorted list, then iterate over the list:

class BSTIteratorNaive:
    def __init__(self, root):
        self.sorted_vals = []
        self.index = 0
        self._inorder(root)

    def _inorder(self, node):
        if not node:
            return
        self._inorder(node.left)
        self.sorted_vals.append(node.val)
        self._inorder(node.right)

    def next(self):
        val = self.sorted_vals[self.index]
        self.index += 1
        return val

    def hasNext(self):
        return self.index < len(self.sorted_vals)

This uses O(n) space. Can we do better?

The optimal approach: Controlled in-order with a stack

The idea is to use a stack that always holds the leftmost path from the current position. Each call to next() pops the top, then pushes the leftmost path from the right child.

class BSTIterator:
    def __init__(self, root):
        self.stack = []
        self._push_left(root)

    def _push_left(self, node):
        """Push all left children onto the stack."""
        while node:
            self.stack.append(node)
            node = node.left

    def next(self):
        """Return the next smallest element."""
        node = self.stack.pop()

        # If this node has a right child, push its leftmost path
        if node.right:
            self._push_left(node.right)

        return node.val

    def hasNext(self):
        """Return True if there are more elements."""
        return len(self.stack) > 0

How the stack evolves

BST:        7
           / \
          3   15
             / \
            9   20

Initial stack (push left from 7): [7, 3]

next() → pop 3, no right child. Stack: [7]
next() → pop 7, right child is 15, push left from 15: [15, 9]
next() → pop 9, no right child. Stack: [15]
next() → pop 15, right child is 20, push left from 20: [20]
next() → pop 20. Stack: []
hasNext() → False

Output: 3, 7, 9, 15, 20  ✓ (sorted!)

Complexity

Metric	Value
Time per next()	Amortized O(1) — each node is pushed and popped exactly once across all calls
Space	O(h) — stack holds at most h nodes (height of tree)

The amortized O(1) is the key insight. Although a single next() call might push multiple nodes, across n calls the total pushes are exactly n.

---

Problem 2: Range Sum of BST (LeetCode 938)

Given a BST and a range [low, high], return the sum of all node values within that range.

        10
       /  \
      5    15
     / \     \
    3   7    18

low = 7, high = 15
Answer: 7 + 10 + 15 = 32

Recursive approach

def range_sum_bst(root, low, high):
    """Sum all values in [low, high] in the BST."""
    if not root:
        return 0

    # If current value is too small, only search right
    if root.val < low:
        return range_sum_bst(root.right, low, high)

    # If current value is too large, only search left
    if root.val > high:
        return range_sum_bst(root.left, low, high)

    # Current value is in range — include it and search both subtrees
    return (root.val
            + range_sum_bst(root.left, low, high)
            + range_sum_bst(root.right, low, high))

Iterative approach

from collections import deque

def range_sum_bst_iterative(root, low, high):
    """Range sum using iterative DFS."""
    if not root:
        return 0

    total = 0
    stack = [root]

    while stack:
        node = stack.pop()
        if not node:
            continue

        if node.val < low:
            stack.append(node.right)
        elif node.val > high:
            stack.append(node.left)
        else:
            total += node.val
            stack.append(node.left)
            stack.append(node.right)

    return total

Complexity

Metric	Value
Time	O(n) worst case, but often much better — we prune branches outside the range
Space	O(h)

---

Problem 3: Count Nodes in Range

Count how many nodes have values in [low, high].

def count_in_range(root, low, high):
    """Count nodes with values in [low, high]."""
    if not root:
        return 0

    if root.val < low:
        return count_in_range(root.right, low, high)

    if root.val > high:
        return count_in_range(root.left, low, high)

    return (1
            + count_in_range(root.left, low, high)
            + count_in_range(root.right, low, high))

With augmented BST (subtree sizes)

If each node stores its subtree size, we can answer range queries in O(h):

class AugmentedNode:
    def __init__(self, val=0):
        self.val = val
        self.left = None
        self.right = None
        self.size = 1  # Subtree size including self

def count_less_than(node, val):
    """Count nodes with value strictly less than val."""
    if not node:
        return 0

    if val <= node.val:
        return count_less_than(node.left, val)
    else:
        left_size = node.left.size if node.left else 0
        return left_size + 1 + count_less_than(node.right, val)

def count_in_range_augmented(root, low, high):
    """Count nodes in [low, high] using augmented BST."""
    return count_less_than(root, high + 1) - count_less_than(root, low)

---

Problem 4: Closest Binary Search Tree Value (LeetCode 270)

Given a BST and a target float value, find the node value closest to the target.

        4
       / \
      2   5
     / \
    1   3

Target = 3.7
Closest = 4

Approach: Binary search in BST

def closest_value(root, target):
    """Find the closest value in BST to target."""
    closest = root.val

    while root:
        # Update closest if current is nearer
        if abs(root.val - target) < abs(closest - target):
            closest = root.val

        # Go left or right based on target
        if target < root.val:
            root = root.left
        elif target > root.val:
            root = root.right
        else:
            return root.val  # Exact match

    return closest

Complexity

Metric	Value
Time	O(h)
Space	O(1)

---

Problem 5: Closest K Values (LeetCode 272)

Given a BST, a target value, and an integer k, find the k values in the BST closest to the target.

Approach 1: Inorder + Two pointers

Get the sorted inorder list, then use two pointers to find the k closest.

def closest_k_values(root, target, k):
    """Find k closest values using inorder + two pointers."""
    # Step 1: Get sorted inorder list
    inorder = []

    def dfs(node):
        if not node:
            return
        dfs(node.left)
        inorder.append(node.val)
        dfs(node.right)

    dfs(root)

    # Step 2: Binary search for closest position
    left = 0
    right = len(inorder) - 1

    # Find insertion point
    import bisect
    pos = bisect.bisect_left(inorder, target)

    # Two pointers expanding outward
    left = pos - 1
    right = pos
    result = []

    while len(result) < k:
        if left < 0:
            result.append(inorder[right])
            right += 1
        elif right >= len(inorder):
            result.append(inorder[left])
            left -= 1
        elif abs(inorder[left] - target) <= abs(inorder[right] - target):
            result.append(inorder[left])
            left -= 1
        else:
            result.append(inorder[right])
            right += 1

    return result

Approach 2: Two stacks (predecessor/successor iterators)

This approach uses O(h) space instead of O(n) by maintaining two stacks — one iterating backward (predecessors) and one forward (successors).

def closest_k_values_stacks(root, target, k):
    """Find k closest values using predecessor/successor stacks."""
    # Predecessor stack: iterate in reverse inorder (descending)
    pred_stack = []
    # Successor stack: iterate in inorder (ascending)
    succ_stack = []

    # Initialize: push path to target
    node = root
    while node:
        if target < node.val:
            succ_stack.append(node)
            node = node.left
        elif target > node.val:
            pred_stack.append(node)
            node = node.right
        else:
            succ_stack.append(node)
            pred_stack.append(node)
            break

    def next_predecessor():
        """Get next smaller value."""
        if not pred_stack:
            return float('-inf')
        node = pred_stack.pop()
        val = node.val
        # Push rightmost path of left subtree
        node = node.left
        while node:
            pred_stack.append(node)
            node = node.right
        return val

    def next_successor():
        """Get next larger value."""
        if not succ_stack:
            return float('inf')
        node = succ_stack.pop()
        val = node.val
        # Push leftmost path of right subtree
        node = node.right
        while node:
            succ_stack.append(node)
            node = node.left
        return val

    result = []
    pred_val = next_predecessor()
    succ_val = next_successor()

    # Skip duplicate if target exists in tree
    if pred_val == succ_val:
        result.append(pred_val)
        pred_val = next_predecessor()
        succ_val = next_successor()

    while len(result) < k:
        if abs(pred_val - target) <= abs(succ_val - target):
            result.append(pred_val)
            pred_val = next_predecessor()
        else:
            result.append(succ_val)
            succ_val = next_successor()

    return result

Complexity comparison

Approach	Time	Space
Inorder + two pointers	O(n)	O(n)
Two stacks	O(h + k)	O(h)

The two-stack approach is better when k is much smaller than n.

---

Problem 6: BST Range Traversal

Print all BST values in a given range in sorted order:

def range_traversal(root, low, high):
    """Print all values in [low, high] in sorted order."""
    result = []

    def inorder(node):
        if not node:
            return

        # Only go left if there might be values >= low
        if node.val > low:
            inorder(node.left)

        # Include current if in range
        if low <= node.val <= high:
            result.append(node.val)

        # Only go right if there might be values <= high
        if node.val < high:
            inorder(node.right)

    inorder(root)
    return result

---

Using BST Iterator for Merge Operations

The BST iterator is powerful for merging two BSTs:

def merge_two_bsts(root1, root2):
    """Merge two BSTs into a single sorted list."""
    iter1 = BSTIterator(root1)
    iter2 = BSTIterator(root2)

    result = []
    val1 = iter1.next() if iter1.hasNext() else float('inf')
    val2 = iter2.next() if iter2.hasNext() else float('inf')

    while val1 != float('inf') or val2 != float('inf'):
        if val1 <= val2:
            result.append(val1)
            val1 = iter1.next() if iter1.hasNext() else float('inf')
        else:
            result.append(val2)
            val2 = iter2.next() if iter2.hasNext() else float('inf')

    return result

This merges in O(n + m) time with O(h1 + h2) space — much better than flattening both trees first.

---

Two-Sum in BST Using Two Iterators

Check if any two nodes in a BST sum to a target:

class BSTReverseIterator:
    """Iterates BST in descending order."""
    def __init__(self, root):
        self.stack = []
        self._push_right(root)

    def _push_right(self, node):
        while node:
            self.stack.append(node)
            node = node.right

    def next(self):
        node = self.stack.pop()
        if node.left:
            self._push_right(node.left)
        return node.val

    def hasNext(self):
        return len(self.stack) > 0


def two_sum_bst(root, target):
    """Check if two nodes sum to target using two iterators."""
    forward = BSTIterator(root)
    backward = BSTReverseIterator(root)

    left = forward.next()
    right = backward.next()

    while left < right:
        current_sum = left + right
        if current_sum == target:
            return True
        elif current_sum < target:
            left = forward.next()
        else:
            right = backward.next()

    return False

Complexity

Metric	Value
Time	O(n)
Space	O(h) — two stacks of height h

---

Common Mistakes

1. Forgetting amortized analysis — the BST iterator’s next() is O(1) amortized, not O(h) per call. Each node is pushed and popped exactly once across all calls.

2. Not pruning in range queries — if root.val {'<'} low, don’t bother searching the left subtree. The BST property lets you skip entire branches.

3. Integer overflow in closest value — when computing abs(val - target), use floating point or be careful with large integers.

4. Returning wrong type for closest K — the problem asks for values, not nodes. Don’t return TreeNode objects.

---

Practice Problems

Problem	Platform	Difficulty
Binary Search Tree Iterator	LeetCode 173	Medium
Range Sum of BST	LeetCode 938	Easy
Closest Binary Search Tree Value	LeetCode 270	Easy
Closest Binary Search Tree Value II	LeetCode 272	Hard
Two Sum IV - Input is a BST	LeetCode 653	Easy
Kth Smallest Element in a BST	LeetCode 230	Medium

---

Key Takeaways

• The BST iterator with a stack is the controlled in-order traversal — O(h) space, O(1) amortized per next().
• Range queries exploit the BST property to prune entire branches, often visiting far fewer than n nodes.
• Closest value is essentially binary search on a tree — O(h) time, O(1) space.
• Closest K values with two stacks gives O(h + k) time — optimal when k is small.
• The iterator pattern enables merge and two-sum operations with minimal space.
• Always think about whether you can leverage BST ordering to skip subtrees.