BST Iterator

March 2026 · 10 min read

You have a BST and want to visit its nodes in sorted order, but not all at once. Maybe you're merging two BSTs, implementing a database cursor, or building a lazy range query. You need an iterator: call next() to get the next smallest value, call hasNext() to check if more values remain.

The naive approach is to flatten the tree into a sorted array during construction, then iterate over the array. That works but uses O(n) space upfront. The elegant approach uses an explicit stack to simulate in-order traversal, yielding one element at a time with O(h) space.

The Problem

Implement the BSTIterator class (LeetCode 173):

• BSTIterator(root) : Initialize the iterator over the BST rooted at root.
• next() : Return the next smallest number in the BST.
• hasNext() : Return true if there are still numbers left to visit.

All calls to next() are guaranteed to be valid (there will be at least one next number).

Naive Approach: Flatten to Array

Do a full in-order traversal upfront, store results in a vector, and use an index to iterate:

class BSTIterator {
    std::vector<int> sorted;
    int idx = 0;
public:
    BSTIterator(TreeNode* root) {
        inorder(root);
    }
    int next() { return sorted[idx++]; }
    bool hasNext() { return idx < sorted.size(); }
private:
    void inorder(TreeNode* node) {
        if (!node) return;
        inorder(node->left);
        sorted.push_back(node->val);
        inorder(node->right);
    }
};

This works, but uses O(n) space and O(n) initialization time. For a tree with millions of nodes where you only need the first 10 values, this is wasteful.

Stack-Based Approach: Controlled In-Order Traversal

The key insight: in-order traversal visits nodes in the order left, root, right. We can simulate this with an explicit stack by "unwinding" the left spine at each step.

The Technique: Push Left Spine

The fundamental operation is pushLeftSpine: starting from a node, push it and all its left descendants onto the stack. This prepares the stack so that the top is always the next smallest unvisited node.

How next() Works

1. Pop the top of the stack. This is the current smallest unvisited node.
2. If the popped node has a right child, call pushLeftSpine on the right child (this prepares the next sequence of nodes).
3. Return the popped node's value.

This mirrors exactly what recursive in-order traversal does: after visiting a node (the "root" of a subtree), you move to its right child and then go as far left as possible.

The Code

class BSTIterator {
    std::stack<TreeNode*> stk;

    void pushLeftSpine(TreeNode* node) {
        while (node) {
            stk.push(node);
            node = node->left;
        }
    }

public:
    BSTIterator(TreeNode* root) {
        pushLeftSpine(root);
    }

    int next() {
        TreeNode* top = stk.top();
        stk.pop();
        pushLeftSpine(top->right);  // prepare right subtree
        return top->val;
    }

    bool hasNext() {
        return !stk.empty();
    }
};

That's the entire implementation. 15 lines of code, and it handles every case correctly.

Detailed Walkthrough

Let's trace through the calls for the tree [15, 7, 20, 3, 9, 18, 25]:

Step-Through Animation

Click Step to call next(). Watch the stack change and nodes get visited in sorted order.

Complexity Analysis

At first glance, next() looks like it could be O(h) in the worst case (when pushLeftSpine traverses a long left spine). But across all n calls to next(), each node is pushed and popped exactly once. So:

Space: O(h) for the stack. For a balanced BST, h = O(log n). This is much better than the O(n) of the flatten approach.

Why Not Use Parent Pointers?

If nodes store parent pointers, you can implement an iterator without a stack at all. After visiting a node:

• If it has a right child, go to the right child and then as far left as possible.
• Otherwise, go up to the parent, and keep going up until you arrive from a left child.

class BSTIterator {
    TreeNode* cur;

    TreeNode* leftmost(TreeNode* n) {
        while (n && n->left) n = n->left;
        return n;
    }

public:
    BSTIterator(TreeNode* root) : cur(leftmost(root)) {}

    int next() {
        int val = cur->val;
        if (cur->right) {
            cur = leftmost(cur->right);
        } else {
            // Go up until we come from a left child
            while (cur->parent && cur == cur->parent->right)
                cur = cur->parent;
            cur = cur->parent;
        }
        return val;
    }

    bool hasNext() { return cur != nullptr; }
};

O(1) space, O(1) amortized time. But this requires parent pointers, which most tree implementations (and interview problems) don't provide. The stack-based approach is the universal solution.

Variations and Extensions

Reverse Iterator (Descending Order)

Mirror the approach: push the right spine instead of the left. next() pops the top and pushes the left spine of the popped node's left child.

class BSTReverseIterator {
    std::stack<TreeNode*> stk;

    void pushRightSpine(TreeNode* node) {
        while (node) {
            stk.push(node);
            node = node->right;
        }
    }

public:
    BSTReverseIterator(TreeNode* root) { pushRightSpine(root); }

    int next() {
        TreeNode* top = stk.top(); stk.pop();
        pushRightSpine(top->left);
        return top->val;
    }

    bool hasNext() { return !stk.empty(); }
};

Two-Pointer on BST (Two Sum)

With both a forward and reverse iterator, you can solve "Two Sum in BST" using the classic two-pointer technique:

bool findTarget(TreeNode* root, int k) {
    BSTIterator lo(root);
    BSTReverseIterator hi(root);

    int left = lo.next(), right = hi.next();
    while (left < right) {
        int sum = left + right;
        if (sum == k) return true;
        if (sum < k) left = lo.next();
        else right = hi.next();
    }
    return false;
}
// Time: O(n), Space: O(h)

Range Query Iterator

To iterate only over values in range [lo, hi], modify pushLeftSpine to skip nodes that are entirely out of range:

void pushLeftSpine(TreeNode* node, int lo) {
    while (node) {
        if (node->val >= lo) {
            stk.push(node);
            node = node->left;
        } else {
            node = node->right;  // skip left subtree (all < lo)
        }
    }
}

int next(int hi) {
    TreeNode* top = stk.top(); stk.pop();
    if (top->val > hi) return -1;  // out of range
    pushLeftSpine(top->right, lo);
    return top->val;
}

Merge K Sorted BSTs

Create one iterator per BST, then use a min-heap of iterators to merge them in sorted order. Each heap operation is O(log k) where k is the number of BSTs:

std::vector<int> mergeKBSTs(std::vector<TreeNode*>& roots) {
    auto cmp = [](auto& a, auto& b) { return a.peek() > b.peek(); };
    std::priority_queue<BSTIterator, std::vector<BSTIterator>,
                        decltype(cmp)> pq(cmp);

    for (auto* r : roots)
        if (r) pq.push(BSTIterator(r));

    std::vector<int> result;
    while (!pq.empty()) {
        auto it = pq.top(); pq.pop();
        result.push_back(it.next());
        if (it.hasNext()) pq.push(it);
    }
    return result;
}
// Time: O(N log k), Space: O(k * h)

Real-World Usage

• Database cursors: When you run SELECT * FROM users ORDER BY age, the database traverses its B-tree index using an iterator. It doesn't load all matching rows at once; it yields them one at a time.
• std::set / std::map: The C++ standard library's ordered containers use red-black trees internally. Their begin() and ++ operators implement exactly this iterator pattern (using parent pointers).
• Merge joins: When joining two sorted tables, the database opens an iterator on each table's index and advances them in tandem, exactly like the merge step of merge sort.
• Lazy evaluation: In functional programming, BST iterators enable lazy traversal. You only compute the next element when you actually need it.

Interview Tips

Practice Problems