Binary Search Tree Iterator - Solution & Explanation

Problem Overview: Design an iterator for a Binary Search Tree that returns nodes in ascending order. The iterator exposes two operations: next() which returns the next smallest value and hasNext() which tells you if more nodes exist.

Approach 1: Using Stack for Controlled In-order Traversal (Time: O(1) average per operation, Space: O(h))

A BST's in-order traversal naturally produces values in sorted order. Instead of generating the entire traversal upfront, maintain a stack that simulates the recursion of in-order traversal. During initialization, push all nodes from the root down to the leftmost node. The top of the stack always represents the next smallest element.

When next() is called, pop the top node from the stack and return its value. If that node has a right child, push the right child and all of its left descendants onto the stack. This ensures the stack always holds the next valid traversal path. hasNext() simply checks whether the stack is empty.

This approach keeps only the traversal path in memory, not the entire tree. Each node is pushed and popped at most once, so the total traversal cost is O(n) across all calls, which makes each next() amortized O(1). Space usage is O(h), where h is the tree height. This method relies on a stack to simulate recursion and is the standard solution used in interviews.

Approach 2: Morris In-order Traversal (Time: O(1) average per operation, Space: O(1))

Morris traversal removes the need for an explicit stack by temporarily modifying the binary tree. The idea is to create a temporary "thread" from each node's in-order predecessor back to the current node. This allows the algorithm to return to a parent node after finishing its left subtree without recursion or a stack.

While iterating, if the current node has no left child, it is the next smallest element and the iterator moves to its right child. If a left child exists, find the rightmost node in that left subtree (the in-order predecessor). If the predecessor's right pointer is null, create a temporary link to the current node and move left. If the link already exists, remove it, output the current node, and move right.

Morris traversal visits each node at most twice and maintains O(1) extra space. The tradeoff is that the tree structure is temporarily modified during iteration, which can make the implementation more complex and less desirable in production iterators.

Recommended for interviews: The stack-based controlled in-order traversal is what interviewers typically expect. It clearly demonstrates understanding of BST ordering and iterative traversal using a stack. Mentioning Morris traversal shows deeper knowledge of tree traversal optimizations, but the stack approach is easier to reason about and aligns better with real iterator design.