Binary Search Tree Iterator Medium 0 attempts
LeetCode ↗

Binary Search Tree Iterator

Medium TreeBinary TreeDFS LeetCode

Implement a BST iterator that supports next() (returns next smallest element) and hasNext() operations, both running in average O(1) time with O(h) memory.

Example: BST = [7,3,15,null,null,9,20] → next() calls return: 3, 7, 9, 15, 20

Sample Input
—
Sample Output
—
Constraints
  • 1 <= number of nodes <= 10^5
  • 0 <= Node.val <= 10^6
  • At most 10^5 calls to next() and hasNext()
Topics
TreeBinary TreeDFS

Controlled Inorder with Stack

Maintain a stack of left-spine nodes. On next(), pop and push right subtree's left spine.

class BSTIterator {
  constructor(root) {
    this.stack = [];
    this._pushLeft(root);
  }
  _pushLeft(node) {
    while (node) { this.stack.push(node); node = node.left; }
  }
  next() {
    const node = this.stack.pop();
    this._pushLeft(node.right);
    return node.val;
  }
  hasNext() { return this.stack.length > 0; }
}

Time: O(1) amortized | Space: O(h)

Saved in this browser only. Private to you.

JavaScript