loading

Binary Search Tree Iterator — Step-by-Step Visualization

mediumLeetCode #173StackTreeDesignBinary Search TreeBinary TreeIterator

Implement iterator over BST inorder traversal. next() returns next smallest. hasNext() returns true if more.

Algorithm Pattern

Lazy Inorder with Stack

Key Idea

Push only left spine; each next() pops and lazily expands right subtree's left spine.

Step-by-Step Approach

  1. Push all left-spine nodes initially
  2. next(): pop top, push left-spine of right child
  3. hasNext(): stack is non-empty

Related Problems