BST Iterator Design in DSA Javascript

Mental Model

A BST iterator lets you see the tree's values one by one in order, like reading a book page by page without loading the whole book at once.

Analogy: Imagine a bookmark in a book that remembers where you stopped reading. Each time you open the book, you continue from that page, not from the start.

      7
     / \
    3   15
       /  \
      9    20

Stack: [7, 3] ↑ (top is 3, next smallest)

Dry Run Walkthrough

Input: BST with nodes 7, 3, 15, 9, 20; iterate to get next smallest values

Goal: Retrieve nodes in ascending order: 3, 7, 9, 15, 20 using the iterator

Step 1: Initialize iterator by pushing leftmost nodes 7 and 3 onto stack

Stack: [7, 3] ↑ (top is 3)

Why: We start at the smallest node by going left as far as possible

Step 2: Call next(): pop 3 from stack, 3 has no right child, so no push

Stack: [7] ↑ (top is 7)

Why: 3 is the smallest node, so we return it and prepare for next

Step 3: Call next(): pop 7 from stack, push leftmost nodes of 7's right child 15 (push 15, then 9)

Stack: [15, 9] ↑ (top is 9)

Why: After 7, next smallest is in right subtree, so we push left path of 15

Step 4: Call next(): pop 9 from stack, 9 has no right child, no push

Stack: [15] ↑ (top is 15)

Why: 9 is next smallest, no right subtree to explore

Step 5: Call next(): pop 15 from stack, push leftmost nodes of 15's right child 20 (push 20)

Stack: [20] ↑ (top is 20)

Why: After 15, next smallest is 20 in right subtree

Step 6: Call next(): pop 20 from stack, 20 has no right child, no push

Stack: [] (empty)

Why: 20 is the largest node, iteration ends

Result:

3 -> 7 -> 9 -> 15 -> 20 -> null

Annotated Code

DSA Javascript

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

class BSTIterator {
  constructor(root) {
    this.stack = [];
    this._pushLeft(root);
  }

  _pushLeft(node) {
    while (node !== null) {
      this.stack.push(node); // push current node
      node = node.left; // move left to find smallest
    }
  }

  next() {
    const node = this.stack.pop(); // pop top node as next smallest
    if (node.right !== null) {
      this._pushLeft(node.right); // push left path of right subtree
    }
    return node.val; // return current smallest
  }

  hasNext() {
    return this.stack.length > 0; // check if more nodes remain
  }
}

// Driver code
const root = new TreeNode(7,
  new TreeNode(3),
  new TreeNode(15, new TreeNode(9), new TreeNode(20))
);
const iterator = new BSTIterator(root);
const result = [];
while (iterator.hasNext()) {
  result.push(iterator.next());
}
console.log(result.join(' -> ') + ' -> null');

this._pushLeft(root);

initialize stack with leftmost nodes to start from smallest

while (node !== null) { this.stack.push(node); node = node.left; }

push all left children to stack to reach smallest node

const node = this.stack.pop();

pop top node as current smallest to return

if (node.right !== null) { this._pushLeft(node.right); }

if right subtree exists, push its leftmost nodes for next smallest

return node.val;

return the value of current smallest node

return this.stack.length > 0;

check if iterator has more nodes to visit

Output

3 -> 7 -> 9 -> 15 -> 20 -> null

Complexity Analysis

Time: O(1) amortized per next() call because each node is pushed and popped once

Space: O(h) where h is tree height, due to stack storing leftmost path

vs Alternative: Compared to inorder traversal storing all nodes (O(n) space), this uses less memory by storing only path nodes

Edge Cases

Empty tree (root is null)

Iterator stack is empty, hasNext() returns false immediately

DSA Javascript

this._pushLeft(root);

Tree with single node

Stack contains one node, next() returns that node, then hasNext() is false

DSA Javascript

const node = this.stack.pop();

Tree with only left children

Stack initially contains all nodes, next() pops them in order without pushing new nodes

DSA Javascript

while (node !== null) { this.stack.push(node); node = node.left; }

When to Use This Pattern

When you need to iterate over a BST in sorted order without using extra space for all nodes, use BST Iterator pattern to traverse lazily with a stack.

Common Mistakes

Mistake: Not pushing the leftmost nodes of the right subtree after popping a node
Fix: After popping a node, if it has a right child, push all its left descendants onto the stack

Mistake: Pushing nodes in wrong order causing incorrect traversal sequence
Fix: Always push left children first to ensure smallest nodes are on top of the stack

Summary

It provides a way to get the next smallest element from a BST one at a time.

Use it when you want to traverse a BST in order without storing all nodes at once.

The key is to use a stack to remember the path to the next smallest node.