AlgoMaster Logo

Binary Search Tree Iterator

mediumFrequency8 min readUpdated June 23, 2026

Understanding the Problem

We need to build an iterator that walks through a BST in sorted order, one element at a time. Each call to next() returns the next smallest value, and hasNext() reports whether any values remain.

The word "iterator" is the challenge. We cannot run the whole in-order traversal at once; the traversal has to pause after handing out one value and resume when the caller asks again.

The BST property guarantees that an in-order traversal (left, root, right) visits nodes in ascending order. The problem reduces to implementing a pausable in-order traversal.

Key Constraints:

  • Number of nodes up to 10^5 --> The tree can be large, so storing every value upfront has a real memory cost. The follow-up asks for O(h) space instead.
  • At most 10^5 calls to hasNext and next --> Each call needs to be efficient. O(h) or O(1) per call is ideal.
  • 0 <= Node.val <= 10^6 --> Non-negative values, no special handling needed.

Approach 1: Flatten to Array

Intuition

Separate the traversal from the iteration. The constructor runs a complete in-order traversal of the BST and stores every value in a list. After that, next() returns the next element from the list and hasNext() checks whether the index has reached the end.

All the work happens during construction, so every later call is a constant-time array access. The cost is O(n) space for the list, which is what the follow-up asks us to avoid.

Algorithm

  1. In the constructor, perform an in-order traversal of the BST and store all values in a list.
  2. Maintain an index pointer starting at 0.
  3. For next(), return the value at the current index and increment the index.
  4. For hasNext(), return true if the index is less than the list size.

Example Walkthrough

1Start in-order traversal: go left from root (7 → 3)
73visit15920
1/7

Code

The next approach runs the same in-order traversal incrementally, keeping only the current root-to-node path in memory. That cuts the extra space from O(n) to O(h).

Approach 2: Controlled Recursion with Stack (Optimal)

Intuition

An iterative in-order traversal uses a stack: push left children until you reach the smallest node, then pop, process the node, and move into its right subtree. The iterator runs that same loop, but it stops after each processed node instead of running to completion. The stack is the saved state of the paused traversal.

The stack holds the nodes whose left subtrees the traversal has entered but which it has not yet returned, and the top of the stack is always the next node in sorted order. The constructor pushes the root and all its left descendants, which places the minimum on top. Each next() pops a node, and if that node has a right child, pushes the right child along with all of its left descendants. This keeps the invariant intact, because the leftmost node of the right subtree is the popped node's in-order successor.

The stack stays within O(h): every node on it lies inside the left subtree of the node below it, so the entries form a single descending path from the root, and a path holds at most h nodes. This matches the follow-up's space bound.

Algorithm

  1. In the constructor, initialize an empty stack. Push the root and all its left descendants onto the stack (this navigates to the smallest element).
  2. For next():
    • Pop the top node from the stack (this is the next smallest value).
    • If the popped node has a right child, push the right child and all of its left descendants onto the stack.
    • Return the popped node's value.
  3. For hasNext(), return true if the stack is not empty.

Example Walkthrough

BST
1Constructor: push leftmost path (7, 3). Stack: [7, 3]
73top15920
stack
1Push leftmost path: 7, then 3. Top = 3 (smallest)
7
3
Top
1/6

Code

The stack meets the follow-up's O(h) bound. Morris traversal removes even that, storing the traversal's return path in the tree itself.

Approach 3: Morris Traversal (O(1) Space)

Intuition

The stack in Approach 2 exists to remember the way back: after a left subtree is finished, the traversal must return to the unfinished ancestor. Morris traversal stores that return path in the tree instead. Before descending into a node's left subtree, it finds the subtree's rightmost node, which is the node's in-order predecessor, and points that node's unused right pointer back at the current node. This temporary link is called a thread. When the traversal later runs off the end of the left subtree and follows the thread, it arrives back at the ancestor with no stack involved. On this second arrival the thread is removed, so the tree regains its original shape as the traversal moves past each node.

The iterator state is a single pointer, curr. Each next() call runs the Morris loop until it produces one value, then stops. hasNext() reduces to checking curr != null. A returned node moves curr to its right pointer, and at that moment a null right pointer can only mean one of two things: either the node is the maximum (no successor exists), or it would have been threaded. Any non-maximum node with no real right child is the rightmost node of its successor's left subtree, so its right pointer holds a thread to that successor when it is visited. curr therefore becomes null exactly when the last value has been returned.

The trade-off is mutation. While iteration is in progress the tree contains threads, so this version cannot be used while other code reads the tree concurrently, and abandoning the iteration partway leaves the tree modified.

Algorithm

  1. In the constructor, set curr to the root. Nothing else is stored.
  2. For next(), loop until a value is produced:
    • If curr has no left child, record curr.val, move curr to curr.right, and return the value.
    • Otherwise, find the in-order predecessor pred: start at curr.left and follow right pointers until the next one is null or points back at curr.
    • If pred.right is null, create the thread: set pred.right = curr and move curr to curr.left.
    • If pred.right is curr, the left subtree is finished: remove the thread by setting pred.right = null, record curr.val, move curr to curr.right, and return the value.
  3. For hasNext(), return curr != null.

Example Walkthrough

1Constructor: curr = 7. No traversal work happens yet
7curr315920
1/8

Code