Why BST Iterator Design in DSA Javascript?

The Big Idea

What if you could flip through a huge sorted list one item at a time, without losing your place or wasting time?

The Scenario

Imagine you have a huge family tree drawn on paper, and you want to look at each member in order from youngest to oldest. You try to scan the whole paper every time you want the next person, but it takes forever and you lose your place easily.

The Problem

Manually scanning the entire tree each time is slow and confusing. You might miss someone or look at the same person twice. It's hard to remember where you left off without a clear system.

The Solution

A BST Iterator acts like a bookmark and a guide. It remembers where you are and quickly gives you the next member in order without scanning everything again. It makes moving through the tree smooth and easy.

Before vs After

✗ Before

function getNextInOrder(root) {
  let nodes = [];
  function inorder(node) {
    if (!node) return;
    inorder(node.left);
    nodes.push(node.val);
    inorder(node.right);
  }
  inorder(root);
  return nodes.shift();
}

✓ After

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

What It Enables

This design lets you explore a binary search tree step-by-step in order, using little memory and no repeated work.

Real Life Example

Think of browsing a sorted list of contacts on your phone. Instead of loading all contacts at once, the phone shows one contact at a time as you scroll, remembering where you left off.

Key Takeaways

Manual scanning of trees is slow and error-prone.

BST Iterator remembers position and efficiently returns next item.

It enables smooth, ordered traversal with minimal memory.