Binary Search Tree Iterator Medium 0 attempts
LeetCode ↗

Binary Search Tree Iterator

Medium TreeBinary TreeDFS LeetCode

Design an iterator over a binary search tree that walks its values in ascending order. It should expose next(), which returns the next-smallest value each time it's called, and hasNext(), which reports whether any values remain — both running in average O(1) time while using only O(h) extra memory, where h is the tree's height.

Calls to next() occur only when hasNext() is true.

Input Format
Implement the class BSTIterator. Fixtures contain constructor arguments and a list of [method, ...arguments] calls. Each fixture starts with a fresh instance. Trees use level-order arrays with null for missing children. The editor passes nodes with val, left, and right properties; [] becomes null.
Output Format
Return the specified result from each method. The displayed output lists results in call order; undefined results appear as null.

Sample Input and Output

Example 1 · Run Sample

Input
constructorArgs = [[7,3,15,null,null,9,20]]
operations = [["next"],["next"],["hasNext"],["next"],["next"],["next"],["hasNext"]]
Output
[3,7,true,9,15,20,false]

Example 2

Input
constructorArgs = [[1]]
operations = [["hasNext"],["next"],["hasNext"]]
Output
[true,1,false]
Constraints
  • 1 <= number of nodes <= 10^5
  • 0 <= Node.val <= 10^6
  • At most 10^5 calls to next() and hasNext()
Test Cases (2)
Case 1
Args: [[[7,3,15,null,null,9,20]],[["next"],["next"],["hasNext"],["next"],["next"],["next"],["hasNext"]]] Expected: [3,7,true,9,15,20,false]
Case 2
Args: [[[1]],[["hasNext"],["next"],["hasNext"]]] Expected: [true,1,false]
Topics
TreeBinary TreeDFS

Controlled Inorder with Stack

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

javascript
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