BST Iterator Design in DSA Javascript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main purpose of a BST Iterator?

A BST Iterator allows you to traverse a Binary Search Tree (BST) in sorted order (in-order traversal) efficiently, providing next smallest elements one by one without traversing the entire tree at once.

intermediate

How does a BST Iterator typically store its state internally?

It uses a stack to keep track of nodes. The stack stores the path from the root to the current node, allowing the iterator to return the next smallest element and move forward efficiently.

beginner

Explain the role of the 'hasNext()' method in a BST Iterator.

'hasNext()' checks if there are more nodes to visit in the BST. It returns true if the stack is not empty, meaning there are still nodes left to traverse in sorted order.

intermediate

What does the 'next()' method do in a BST Iterator?

'next()' returns the next smallest value in the BST. It pops the top node from the stack, processes it, and pushes all the left children of the popped node's right subtree onto the stack.

intermediate

Why is a stack used instead of recursion in BST Iterator design?

Using a stack explicitly avoids recursion overhead and allows the iterator to pause and resume traversal efficiently, providing one element at a time without traversing the whole tree upfront.

What traversal order does a BST Iterator follow to return elements?

A Pre-order traversal

B Level-order traversal

C Post-order traversal

D In-order traversal

A BST Iterator returns elements in sorted order, which corresponds to in-order traversal of the BST.

What data structure is commonly used inside a BST Iterator to track nodes?

A Queue

B Stack

C Linked List

D Hash Map

A stack is used to keep track of nodes during in-order traversal in a BST Iterator.

What does the 'hasNext()' method return when the BST Iterator has no more elements?

A false

B null

C true

D undefined

'hasNext()' returns false when there are no more nodes left to traverse.

When 'next()' is called, which nodes are pushed onto the stack?

A All left children of the popped node's right subtree

B All nodes in the tree

C All left children of the popped node

D All right children of the popped node

'next()' pushes all left children of the popped node's right subtree to maintain in-order traversal.

Why is the BST Iterator efficient for large trees?

A It traverses the entire tree at once

B It uses recursion to speed up traversal

C It returns elements one by one without full traversal upfront

D It stores all nodes in an array first

The iterator returns elements one by one, using a stack to avoid full traversal upfront, saving time and memory.

Describe how a BST Iterator uses a stack to return the next smallest element.

Think about how in-order traversal visits nodes left-root-right.

Explain the difference between using recursion and a stack in BST Iterator design.

Consider how recursion and stack manage traversal state.

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