Log inSign up
mediumLeetCodeNot Started

BST Iterator

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

BST
Solve on LeetCode
Lesson

Problem Statement

Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST): - BSTIterator(TreeNode root): Initializes an object of the BSTIterator class. The root of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST. - boolean hasNext(): Returns true if there exists a number in the traversal to the right of the pointer, otherwise returns false. - int next(): Moves the pointer to the right, then returns the number at the pointer.

Notice that by initializing the pointer to a non-existent smallest number, the first call to next() will return the smallest element in the BST.

You may assume that next() calls will always be valid. That is, there will be at least a next number in the in-order traversal when next() is called.

Follow up: Could you implement next() and hasNext() to run in average O(1) time and use O(h) memory, where h is the height of the tree?

Constraints:

  • The number of nodes in the tree is in the range [1, 105].
  • 0 <= Node.val <= 106
  • At most 105 calls will be made to hasNext, and next.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Implement a lazy, stream-like iterator that yields BST elements on demand.
  • Prove why pushing right children's left spines achieves amortized O(1) time.
  • Optimize tree traversals to operate within O(H) auxiliary space bounds.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Iterate through BST in sorted order one element at a time.
  • O(H) memory constraint instead of O(N).
  • Design iterator interface (hasNext / next).

Algorithmic Decision Tree:

  • If O(N) memory allowed -> Flatten via inorder into array or queue.
  • If O(H) memory requested -> Custom stack storing left spine.

Connected Patterns:

Binary Tree Inorder TraversalInorder Successor in BSTFlatten Binary Tree to Linked List

1. Precomputed Inorder Array

Intuition

Run a full inorder traversal in the constructor and store all N node values in a list. Maintain an index pointer pointing to the current element. hasNext() checks idx < list.size(), and next() returns list[idx++].

When to apply: Simple baseline when O(N) memory is acceptable.

Algorithm

  1. Step 1: Traverse tree inorder, storing values in list.
  2. Step 2: Initialize index pointer idx = 0.
  3. Step 3: hasNext() returns idx < list.size().
  4. Step 4: next() returns list[idx++].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3using namespace std;
4
5struct TreeNode {
6 int val;
7 TreeNode *left, *right;
8 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9};
10
11class BSTIterator {
12 vector<int> vals;
13 int idx = 0;
14 void inorder(TreeNode* node) {
15 if (!node) return;
16 inorder(node->left);
17 vals.push_back(node->val);
18 inorder(node->right);
19 }
20public:
21 BSTIterator(TreeNode* root) {
22 inorder(root);
23 }
24 int next() {
25 return vals[idx++];
26 }
27 bool hasNext() {
28 return idx < vals.size();
29 }
30};
31
32int main() {
33 TreeNode* root = new TreeNode(7);
34 root->left = new TreeNode(3);
35 root->right = new TreeNode(15);
36 BSTIterator it(root);
37 cout << it.next() << " " << it.next() << " " << boolalpha << it.hasNext() << endl;
38 return 0;
39}

Time & Space Complexity

  • Time complexity: O(N) constructor, O(1) next() and hasNext()
  • Space complexity: O(N) memory

2. Generator / Coroutine Yield

Intuition

Define a generator function that yields each node during recursive or iterative inorder traversal. hasNext() checks if the iterator has reached its end, and next() advances the generator.

When to apply: Modern high-level languages (Python generators, JS generator functions).

Algorithm

  1. Step 1: Create recursive generator yielding node.val inorder.
  2. Step 2: Buffer next value or use standard iterator protocol.
  3. Step 3: hasNext() checks for available yield, next() returns yielded value.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <stack>
3using namespace std;
4
5struct TreeNode {
6 int val;
7 TreeNode *left, *right;
8 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9};
10
11class BSTIterator {
12 stack<TreeNode*> st;
13public:
14 BSTIterator(TreeNode* root) {
15 for (TreeNode* curr = root; curr; curr = curr->left) st.push(curr);
16 }
17 int next() {
18 TreeNode* node = st.top(); st.pop();
19 for (TreeNode* curr = node->right; curr; curr = curr->left) st.push(curr);
20 return node->val;
21 }
22 bool hasNext() {
23 return !st.empty();
24 }
25};
26
27int main() {
28 TreeNode* root = new TreeNode(7, new TreeNode(3), new TreeNode(15));
29 BSTIterator it(root);
30 cout << it.next() << " " << it.next() << " " << it.hasNext() << endl;
31 return 0;
32}

Time & Space Complexity

  • Time complexity: Amortized O(1) per step
  • Space complexity: O(H) call stack

3. Controlled Stack Left-Spine Traversal (O(H) Memory, Amortized O(1))

Intuition

Maintain an explicit stack. A helper pushAllLeft(node) pushes node and repeatedly follows node = node.left until reaching null. In the constructor, call pushAllLeft(root). hasNext() returns !stack.empty(). next() pops node, calls pushAllLeft(node.right), and returns node.val.

When to apply: The universally demanded Gold Standard interview solution.

Algorithm

  1. Step 1: Helper pushAllLeft(node): while node != null: stack.push(node); node = node.left;.
  2. Step 2 (Constructor): pushAllLeft(root).
  3. Step 3: hasNext() returns !stack.empty() in O(1).
  4. Step 4: next(): curr = stack.pop(); call pushAllLeft(curr.right); return curr.val.

BST Iterator Trace

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Init with root 7 -> stack [7, 3]
Visual state
Values and pointers at this exact step
tree
This tree trace has no visual items for the current step yet. Add step.items (and connections where needed) to render its structure accurately.
Decision / next transition
Step 1
Why this step matters

Init with root 7 -> stack [7, 3]. Lowest element 3 is on top.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <stack>
3using namespace std;
4
5struct TreeNode {
6 int val;
7 TreeNode *left, *right;
8 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9};
10
11class BSTIterator {
12 stack<TreeNode*> st;
13 void pushAllLeft(TreeNode* node) {
14 while (node) {
15 st.push(node);
16 node = node->left;
17 }
18 }
19public:
20 BSTIterator(TreeNode* root) {
21 pushAllLeft(root);
22 }
23 int next() {
24 TreeNode* tmp = st.top();
25 st.pop();
26 pushAllLeft(tmp->right);
27 return tmp->val;
28 }
29 bool hasNext() {
30 return !st.empty();
31 }
32};
33
34int main() {
35 TreeNode* root = new TreeNode(7);
36 root->left = new TreeNode(3);
37 root->right = new TreeNode(15);
38 root->right->left = new TreeNode(9);
39 root->right->right = new TreeNode(20);
40 BSTIterator it(root);
41 cout << "next: " << it.next() << " (exp 3)" << endl;
42 cout << "next: " << it.next() << " (exp 7)" << endl;
43 cout << "hasNext: " << boolalpha << it.hasNext() << endl;
44 cout << "next: " << it.next() << " (exp 9)" << endl;
45 return 0;
46}

Time & Space Complexity

  • Time complexity: Amortized O(1) next(), O(1) hasNext()
  • Space complexity: O(H) auxiliary space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Precomputed ArrayO(N) init, O(1) nextO(N)Flatten tree into array at startup.Memory allocation of N elements.
2.Generator YieldAmortized O(1)O(H)Language generator coroutines.Language runtime coroutine support.
3.Controlled Stack (Optimal)OptimalAmortized O(1)O(H)Push left boundary to stack; expand right children.None. This is optimal.

Common Pitfalls & Crucial Edge Cases

Pushing entire tree into array

Violates the O(H) memory follow-up question.

Forgetting to push left spine of the right child

Upon popping a node, you must push ALL left ancestors of its right child, not just the right child itself.

Null pointer dereference on `next()`

Calling next() when hasNext() is false (though guaranteed valid in problem description, defensive code handles it).

Crucial Edge Cases to Validate:

  • Single-node tree — Stack holds 1 node; first next() returns root value; hasNext() immediately becomes false.
  • Left-skewed tree — All nodes pushed initially; all next() calls simply pop.
  • Right-skewed tree — Stack holds 1 node initially; each next() pops and pushes the next right child.
  • Large tree with 10^5 nodes — O(H) memory prevents memory limit exceeded (MLE).

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the memory bound first: 'By keeping only the left spine on a stack, we reduce auxiliary memory from O(N) to O(H).'
  2. Explain the amortized O(1) proof clearly: each node is pushed once and popped once across the tree's lifetime.
  3. Mention that this pattern forms the foundation of external iterators in standard libraries (like Java's Iterator and C++'s input iterators).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does next() have an AMORTIZED O(1) time complexity even though pushAllLeft can push multiple nodes?

2.What is the maximum number of elements present in the stack at any given moment?

3.What would happen if the tree is completely left-skewed (a linked list 5 -> 4 -> 3 -> 2 -> 1)?

Back to DSA Sheet