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.

Practice

1. What is the main purpose of a BST Iterator in a binary search tree?

easy

A. To traverse the BST in ascending order without recursion

B. To insert new nodes into the BST

C. To delete nodes from the BST

D. To balance the BST automatically

Solution

1. Step 1: Understand BST Iterator functionality

   A BST Iterator is designed to traverse the tree in sorted order, typically ascending, without using recursion.

2. Step 2: Identify the main purpose

   It provides a way to get the next smallest element efficiently, which matches To traverse the BST in ascending order without recursion.

3. Final Answer:

   To traverse the BST in ascending order without recursion -> Option A

4. Quick Check:

   BST Iterator = Ascending traversal without recursion [OK]

Hint: BST Iterator returns next smallest element step-by-step [OK]

Common Mistakes:

• Confusing iterator with insertion or deletion
• Thinking it balances the tree automatically
• Assuming it uses recursion internally

2. Which of the following is the correct way to initialize a BST Iterator class in JavaScript?

easy

A. function BSTIterator(root) { this.stack = []; this.pushRight(root); }

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

C. class BSTIterator { constructor(root) { this.queue = []; this.pushLeft(root); } }

D. function BSTIterator(root) { this.queue = []; this.pushRight(root); }

Solution

1. Step 1: Identify correct class syntax and initialization

   The BST Iterator is usually implemented as a class with a stack to store nodes and a helper method to push left children.

2. Step 2: Check each option

   class BSTIterator { constructor(root) { this.stack = []; this.pushLeft(root); } } correctly uses a class, initializes a stack, and calls pushLeft on root. Others use queue or pushRight which are incorrect for BST Iterator.

3. Final Answer:

   class BSTIterator { constructor(root) { this.stack = []; this.pushLeft(root); } } -> Option B

4. Quick Check:

   Use stack and pushLeft in constructor [OK]

Hint: BST Iterator uses stack and pushLeft method [OK]

Common Mistakes:

• Using queue instead of stack
• Calling pushRight instead of pushLeft
• Using function instead of class syntax

3. Given the BST below and the following code snippet, what will be the output? BST structure: ``` 7 / \ 3 15 / \ 9 20 ``` Code:

const iterator = new BSTIterator(root);
console.log(iterator.next());
console.log(iterator.next());
console.log(iterator.hasNext());

medium

A. [3, 7, false]

B. [7, 9, true]

C. [3, 7, true]

D. [9, 15, true]

Solution

1. Step 1: Trace the first next() call

   First next() returns the smallest element, which is 3.

2. Step 2: Trace the second next() call

   Second next() returns the next smallest, which is 7.

3. Step 3: Check hasNext()

   After two next() calls, there are still nodes (9, 15, 20), so hasNext() returns true.

4. Final Answer:

   [3, 7, true] -> Option C

5. Quick Check:

   next() returns ascending nodes, hasNext() true if more nodes [OK]

Hint: next() returns next smallest; hasNext() true if stack not empty [OK]

Common Mistakes:

• Assuming next() returns root first
• Confusing hasNext() return value
• Ignoring left subtree nodes

4. Consider this buggy BST Iterator method. What is the main error?

next() {
  const node = this.stack.pop();
  if (node.right) {
    this.pushRight(node.right);
  }
  return node.val;
}

pushRight(node) {
  while (node) {
    this.stack.push(node);
    node = node.right;
  }
}

medium

A. next() should not pop from stack

B. next() should return node.key instead of node.val

C. pushRight should use a queue instead of stack

D. pushRight should push left children, not right

Solution

1. Step 1: Analyze pushRight method

   pushRight pushes right children, but BST Iterator needs to push left children to get next smallest.

2. Step 2: Understand correct pushLeft usage

   Correct method pushes left children of right subtree to stack to maintain ascending order.

3. Final Answer:

   pushRight should push left children, not right -> Option D

4. Quick Check:

   Push left children to stack for correct order [OK]

Hint: Push left children of right subtree, not right children [OK]

Common Mistakes:

• Pushing right children instead of left
• Using queue instead of stack
• Returning wrong node property

5. You want to design a BST Iterator that supports next() and hasNext() in O(1) average time and uses O(h) space, where h is tree height. Which approach best achieves this?

hard

A. Use a stack to store left children and push left nodes of right subtree on next()

B. Store all nodes in an array by inorder traversal at initialization

C. Use recursion to traverse nodes on each next() call

D. Use a queue to store nodes level by level

Solution

1. Step 1: Understand time and space constraints

   O(1) average time per next() and O(h) space means no full traversal storage and no recursion per call.

2. Step 2: Evaluate each approach

   Use a stack to store left children and push left nodes of right subtree on next() uses a stack to store left children and pushes left nodes of right subtree on next(), achieving O(1) average time and O(h) space. Store all nodes in an array by inorder traversal at initialization uses O(n) space. Use recursion to traverse nodes on each next() call uses recursion, not O(1) time. Use a queue to store nodes level by level uses queue level order, not inorder.

3. Final Answer:

   Use a stack to store left children and push left nodes of right subtree on next() -> Option A

4. Quick Check:

   Stack + push left children = O(1) avg time, O(h) space [OK]

Hint: Use stack with left children for efficient BST Iterator [OK]

Common Mistakes:

• Storing all nodes wastes space
• Using recursion causes slow next()
• Using queue gives wrong traversal order