BST Iterator Design in DSA C++

Mental Model

A BST iterator lets you visit nodes in order one by one without storing all nodes at once. It uses a stack to remember where to go next.

Analogy: Imagine reading a book with bookmarks. You keep bookmarks on pages you might return to later, so you can continue reading in order without flipping all pages again.

      7
     / \
    3   15
       /  \
      9    20
Stack: Top -> [3,7] (nodes to visit next)
Current -> 3 (next smallest)

Dry Run Walkthrough

Input: BST: 7 -> 3, 15 -> 9, 20; iterate next 4 times

Goal: Visit nodes in ascending order: 3, 7, 9, 15

Step 1: Initialize iterator by pushing left nodes from root

Stack: Top -> [3,7]
Next node to visit is 3

Why: Start at smallest node by going left from root

Step 2: Pop 3 from stack and return it as next

Stack: Top -> [7]
Next node to visit is 7

Why: 3 has no left child, so we return it and move to next

Step 3: Pop 7 from stack and return it as next; push left nodes of 7's right child (15)

Stack: Top -> [9,15]
Next node to visit is 9

Why: After 7, go to right subtree starting at 15, push left nodes

Step 4: Pop 9 from stack and return it as next

Stack: Top -> [15]
Next node to visit is 15

Why: 9 has no left child, so return it and move on

Result:

3 -> 7 -> 9 -> 15 -> ...

Annotated Code

DSA C++

#include <iostream>
#include <stack>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class BSTIterator {
    stack<TreeNode*> stk;

    void pushLeft(TreeNode* node) {
        while (node) {
            stk.push(node); // remember node to visit later
            node = node->left; // go left to find smallest
        }
    }

public:
    BSTIterator(TreeNode* root) {
        pushLeft(root); // initialize stack with left path
    }

    bool hasNext() {
        return !stk.empty(); // if stack empty, no next
    }

    int next() {
        TreeNode* curr = stk.top();
        stk.pop(); // visit current smallest
        pushLeft(curr->right); // after visiting, push left path of right child
        return curr->val;
    }
};

int main() {
    TreeNode* root = new TreeNode(7);
    root->left = new TreeNode(3);
    root->right = new TreeNode(15);
    root->right->left = new TreeNode(9);
    root->right->right = new TreeNode(20);

    BSTIterator it(root);
    while (it.hasNext()) {
        cout << it.next() << " -> ";
    }
    cout << "null" << endl;
    return 0;
}

while (node) { stk.push(node); node = node->left; }

push all left children to stack to reach smallest node

TreeNode* curr = stk.top(); stk.pop();

pop top node as next smallest to return

pushLeft(curr->right);

after visiting node, push left path of its right subtree

return curr->val;

return current node's value as next in order

Output

3 -> 7 -> 9 -> 15 -> 20 -> null

Complexity Analysis

Time: O(1) amortized per next() call because each node is pushed and popped once

Space: O(h) where h is tree height, due to stack storing left path nodes

vs Alternative: Compared to storing all nodes in an array (O(n) space), this uses less memory and supports lazy iteration

Edge Cases

Empty tree

hasNext() returns false immediately, no next() calls possible

DSA C++

return !stk.empty();

Tree with single node

next() returns that node value once, then hasNext() false

DSA C++

while (node) { stk.push(node); node = node->left; }

Right skewed tree (all right children)

stack holds only one node at a time, iteration proceeds linearly

DSA C++

pushLeft(curr->right);

When to Use This Pattern

When you need to iterate a BST in sorted order without extra space for all nodes, use a stack-based iterator to simulate in-order traversal lazily.

Common Mistakes

Mistake: Pushing all nodes into a list at once instead of using a stack for lazy traversal
Fix: Use a stack to push only left children and push right subtree nodes on demand

Mistake: Not pushing left children of the right subtree after popping a node
Fix: After popping a node, call pushLeft on its right child to continue in-order

Summary

It lets you visit BST nodes in ascending order one by one using a stack.

Use it when you want sorted traversal without storing all nodes at once.

The key is to push left children on stack and after visiting a node, push left path of its right child.