← DSA Atlas
Dedicated problem page · #173

Binary Search Tree Iterator

MediumTrees and Binary Search TreesControlled in-order traversal via stackStack-based iterator (lazy in-order)
Solve on LeetCode ↗
173
MediumTrees and Binary Search TreesStack-based iterator (lazy in-order)Controlled in-order traversal via stack

Binary Search Tree Iterator

Implement the BSTIterator class over the in-order traversal of a binary search tree. The constructor takes the root. next() returns the next smallest value in the BST, and hasNext() returns true if a next value exists. next() is only called when hasNext() is true.

Open official problem prompt ↗
In plain English

Emit the BST's values in sorted (in-order) order one call at a time, using memory proportional to the tree height, not its size.

Picture it like this

Like a bookmark in a recursive walk: instead of reading the whole book at once, you keep a stack of the pages you paused on so you can resume exactly where you left off each time next() is called.

Example
Input
["BSTIterator","next","next","hasNext","next","hasNext","next","hasNext","next","hasNext"] with root = [7,3,15,null,null,9,20]
Output
[null,3,7,true,9,true,15,true,20,false]
Why
In-order values are 3,7,9,15,20; next() emits them in that order and hasNext() is false only after 20.
Constraints
The number of nodes is in the range [1, 10^5]0 <= Node.val <= 10^6At most 10^5 calls to next and hasNextnext is called only when hasNext returns true
Pattern lesson

See the pattern, then code

Controlled in-order traversal via stack
Recognition clue

You need in-order values one at a time on demand rather than all at once, which calls for simulating recursion with an explicit stack that pauses between elements.

↗
Trees and Binary Search Trees

Hierarchies, subtree aggregation, path properties, or ordered tree queries.. Keep a stack holding the path of left descendants; the top is always the next smallest, and after popping it you push the left spine of its right subtree.

New words, made simpleKnow these before the algorithm
In-order
Left subtree, node, right subtree — yields BST values ascending
Left spine
The chain of nodes reached by repeatedly following left children
Amortized O(1)
Averaged over all calls, each next() does constant work even though one call may push several nodes
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Precompute full in-order array

Fast per call but stores all n values up front, which the O(h) goal rules out for huge trees.

Traverse once in the constructor into a list, then index through it.

Time O(1)Space O(n)
Best choiceLazy stack of left spine

Uses only stack depth O(h) and stays amortized O(1) per next.

Push only the current left path; expand a node's right subtree when it is popped.

Time O(1)Space O(h)
The rule we keep true

Invariant

The stack always holds, top to bottom, the in-order-next node followed by the ancestors whose values have not yet been emitted.

Why this is correct

Reasoning

Pushing a left spine makes the deepest (smallest) unvisited node the top. After emitting it, its right subtree becomes the next region to explore, so pushing that subtree's left spine restores the invariant that the top is the next smallest. Each node is pushed and popped exactly once, giving amortized O(1).

The algorithm in three movesSay these aloud before coding
1In the constructor push the entire left spine from the root

init stack=[7,3]

2next() pops the top, then pushes the left spine of the popped node's right child

next->3, push right spine of 3 (none), stack=[7]

3Return the popped node's value from next()

next->7, push left spine of 15 -> stack=[15,9]

4hasNext() reports whether the stack is non-empty

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
30
71
92
153
204
1 · Readroot 7
2 · AskWhich nodes form the left spine?
3 · Update statestack=[7,3]
4 · ResultReady; smallest (3) on top
Key takeaway

In-order sequence 3,7,9,15,20 with 3 (leftmost) as the first value returned.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 2-4Prime the stack

    Pushing the root's left spine puts the smallest element on top immediately.

  2. 2
    Lines 6-9Left-spine helper

    Reused by both the constructor and next() to descend all the way left.

  3. 3
    Lines 11-14next()

    Pop the smallest, then queue its right subtree's left spine so the next-smallest is exposed.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • A single-node tree: constructor pushes one node, one next() then hasNext() is false
  • A right-skewed tree still uses O(h) but the spine is short at any moment
  • A left-skewed tree pushes the whole spine at construction
  • Duplicate values are not present in a valid BST here, so ordering is strict
!

Common beginner mistakes

  • Pushing the right subtree's root without descending its left spine, breaking ordering
  • Doing a full traversal in the constructor and defeating the O(h) space goal
  • Calling next() without the stack primed, i.e. forgetting the initial _push_left
Check your understanding

How is next() amortized O(1) when a single call may push many nodes?

More in Trees and Binary Search Trees

#104Maximum Depth of Binary TreePost-order height aggregation#543Diameter of Binary TreePost-order height with a running best#102Binary Tree Level Order TraversalLevel-by-level BFS#98Validate Binary Search TreeRange-bounded validation#236Lowest Common Ancestor of a Binary TreeBottom-up LCA search#105Construct Binary Tree from Preorder and InorderPreorder root + inorder split