BST Iterator Design in DSA C++ - Time & Space Complexity

Time Complexity: BST Iterator Design

O(1) amortized per next()

Understanding Time Complexity

We want to understand how fast the BST Iterator works when moving through a binary search tree.

Specifically, how the time to get the next smallest element changes as the tree grows.

Scenario Under Consideration

Analyze the time complexity of the following BST Iterator code snippet.

class BSTIterator {
  stack<TreeNode*> st;
public:
  BSTIterator(TreeNode* root) {
    while (root) {
      st.push(root);
      root = root->left;
    }
  }

  int next() {
    TreeNode* node = st.top(); st.pop();
    int val = node->val;
    node = node->right;
    while (node) {
      st.push(node);
      node = node->left;
    }
    return val;
  }

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

This code creates an iterator that returns the next smallest value in a BST by using a stack to track nodes.

Identify Repeating Operations

Look at what repeats when calling next():

• Primary operation: Pushing and popping nodes from the stack while traversing left children.
• How many times: Each node is pushed and popped exactly once during the entire iteration.

How Execution Grows With Input

As the tree size n grows, each node is processed once.

Input Size (n)	Approx. Operations
10	About 10 pushes and 10 pops total
100	About 100 pushes and 100 pops total
1000	About 1000 pushes and 1000 pops total

Pattern observation: The total work grows linearly with the number of nodes in the tree.

Final Time Complexity

Time Complexity: O(1) amortized per next()

This means each call to next() takes constant time on average, even though some calls do more work.

Common Mistake

[X] Wrong: "Each call to next() always takes O(h) time, where h is tree height."

[OK] Correct: While some calls do take O(h) time, the total work over all nodes is spread out, so average time per call is O(1).

Interview Connect

Understanding this iterator's time complexity shows you can analyze average work over many operations, a key skill in coding interviews.

Self-Check

"What if we changed the iterator to store all nodes in a sorted list upfront? How would the time complexity of next() change?"