BST Iterator Design in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of BST Iterator next() calls

Given the BST and the iterator code below, what is the output sequence of calling next() four times?

DSA Typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
  }
}

class BSTIterator {
  stack: TreeNode[] = [];

  constructor(root: TreeNode | null) {
    this.pushLeft(root);
  }

  pushLeft(node: TreeNode | null) {
    while (node !== null) {
      this.stack.push(node);
      node = node.left;
    }
  }

  next(): number {
    const node = this.stack.pop()!;
    this.pushLeft(node.right);
    return node.val;
  }

  hasNext(): boolean {
    return this.stack.length > 0;
  }
}

// BST structure:
//       7
//      / \
//     3   15
//         / \
//        9  20

const root = new TreeNode(7,
  new TreeNode(3),
  new TreeNode(15, new TreeNode(9), new TreeNode(20))
);
const iterator = new BSTIterator(root);

const output = [];
for (let i = 0; i < 4; i++) {
  output.push(iterator.next());
}
console.log(output);

A [3, 7, 9, 15]

B [7, 3, 15, 9]

C [3, 9, 7, 15]

D [15, 9, 20, 7]

💡 Hint

Remember that BST Iterator returns nodes in ascending order using in-order traversal.

The BST Iterator uses a stack to traverse the tree in ascending order. The first next() returns 3 (leftmost), then 7 (root), then 9 (left child of 15), then 15 (parent of 9 and 20).

🧠 Conceptual

intermediate

Understanding BST Iterator hasNext() behavior

What does the hasNext() method of a BST Iterator indicate during iteration?

A It returns true if there are still nodes left to visit in ascending order.

B It returns true if the current node has a right child.

C It returns true if the BST is balanced.

D It returns true if the stack is empty.

💡 Hint

Think about what the stack in the iterator represents.

The hasNext() method checks if the stack has nodes left to visit. If yes, it means there are more nodes to return in ascending order.

🔧 Debug

advanced

Identify the error in BST Iterator next() implementation

What error will occur when running the following next() method code in BST Iterator?

DSA Typescript

next(): number {
  const node = this.stack.pop();
  this.pushLeft(node.right);
  return node.val;
}

A SyntaxError due to missing semicolon

B ReferenceError because pushLeft is not defined

C No error, code runs correctly

D TypeError because node can be undefined if stack is empty

💡 Hint

What happens if stack.pop() returns undefined?

If the stack is empty, pop() returns undefined. Accessing node.right or node.val causes a TypeError.

❓ Predict Output

advanced

Output after mixed hasNext() and next() calls

Given the BST Iterator initialized with the BST below, what is the output of the following code?

DSA Typescript

const root = new TreeNode(5,
  new TreeNode(2),
  new TreeNode(8, new TreeNode(6), new TreeNode(10))
);
const iterator = new BSTIterator(root);

const results = [];
while (iterator.hasNext()) {
  if (iterator.next() % 2 === 0) {
    results.push(true);
  } else {
    results.push(false);
  }
}
console.log(results);

A [true, false, true, false, true]

B [true, false, true, true, true]

C [false, false, true, true, false]

D [true, true, false, false, true]

💡 Hint

Check the in-order traversal sequence and test evenness of each value.

In-order traversal: 2 (even → true), 5 (odd → false), 6 (even → true), 8 (even → true), 10 (even → true). Output: [true, false, true, true, true].

🧠 Conceptual

expert

Space complexity of BST Iterator

What is the worst-case space complexity of a BST Iterator implemented with a stack for a BST with n nodes?

A O(log n), where n is the number of nodes in the BST

B O(n), where n is the number of nodes in the BST

C O(h), where h is the height of the BST

D O(1), constant space

💡 Hint

Consider the maximum number of nodes stored in the stack at once.

The stack stores nodes along the path from root to the current node. The maximum size is the height h of the BST, which can be up to n in worst case (skewed tree).

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 storing all elements at once

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 loading all nodes into memory at once.

2. Step 2: Compare options with BST Iterator purpose

   Options B, C, and D relate to modifying the tree, not iterating over it. To traverse the BST in ascending order without storing all elements at once correctly describes the iterator's purpose.

3. Final Answer:

   To traverse the BST in ascending order without storing all elements at once -> Option A

4. Quick Check:

   BST Iterator = In-order traversal on demand [OK]

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

Common Mistakes:

• Confusing iterator with insertion or deletion operations
• Thinking iterator balances the tree
• Assuming iterator stores all nodes at once

2. Which of the following is the correct TypeScript method signature for the next() method in a BST Iterator class that returns the next smallest number?

easy

A. next(value: number): number

B. next(): void

C. next(): number

D. next(): boolean

Solution

1. Step 1: Understand the purpose of next()

   The next() method should return the next smallest number in the BST, so it must return a number.

2. Step 2: Analyze method signatures

   next(): number returns a number with no parameters, which fits the iterator pattern. next(): void returns void, so no value is returned. next(value: number): number takes a parameter, which is not needed. next(): boolean returns boolean, which is incorrect.

3. Final Answer:

   next(): number -> Option C

4. Quick Check:

   next() returns next smallest number [OK]

Hint: next() returns a number without parameters [OK]

Common Mistakes:

• Adding unnecessary parameters to next()
• Returning void instead of number
• Returning boolean instead of number

3. Given the following BST Iterator usage in TypeScript, what will be the output printed?

const root = {
  val: 7,
  left: { val: 3, left: null, right: null },
  right: { val: 15, left: { val: 9, left: null, right: null }, right: { val: 20, left: null, right: null } }
};

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

medium

A. [3, 7, true, 9]

B. [7, 3, true, 9]

C. [3, 7, false, 9]

D. [3, 9, true, 15]

Solution

1. Step 1: Understand BST in-order traversal order

   The BST nodes in ascending order are 3, 7, 9, 15, 20.

2. Step 2: Trace iterator calls

   First next() returns 3, second next() returns 7, hasNext() returns true because more nodes exist, third next() returns 9.

3. Final Answer:

   [3, 7, true, 9] -> Option A

4. Quick Check:

   In-order traversal = 3,7,9,... [OK]

Hint: Remember BST in-order is sorted ascending [OK]

Common Mistakes:

• Mixing up left and right subtree order
• Assuming hasNext() returns next value
• Confusing node values order

4. Consider this partial TypeScript BST Iterator class code. What is the bug?

class BSTIterator {
  stack: TreeNode[] = [];

  constructor(root: TreeNode | null) {
    this.pushLeft(root);
  }

  pushLeft(node: TreeNode | null) {
    while (node !== null) {
      this.stack.push(node);
      node = node.right;  // Bug here
    }
  }

  next(): number {
    const node = this.stack.pop()!;
    this.pushLeft(node.right);
    return node.val;
  }

  hasNext(): boolean {
    return this.stack.length > 0;
  }
}

medium

A. next() should pop from the front, not the end

B. In pushLeft, should traverse left child, not right

C. hasNext() should check if stack is empty incorrectly

D. Constructor should not call pushLeft

Solution

1. Step 1: Analyze pushLeft method

   pushLeft should push all left children to stack to simulate in-order traversal. The code incorrectly moves to node.right instead of node.left.

2. Step 2: Check other methods

   next() correctly pops from stack and pushes left children of right subtree. hasNext() correctly checks stack length. Constructor correctly calls pushLeft.

3. Final Answer:

   In pushLeft, should traverse left child, not right -> Option B

4. Quick Check:

   pushLeft must go left to simulate in-order [OK]

Hint: pushLeft must follow left children, not right [OK]

Common Mistakes:

• Traversing right child in pushLeft instead of left
• Misunderstanding stack usage in iterator
• Incorrect pop direction in next()

5. You want to design a BST Iterator that supports peek() to see the next smallest element without advancing the iterator. Which approach best supports this feature efficiently?

hard

A. Use a queue to store nodes in BFS order

B. Store all BST elements in an array and use an index pointer

C. Traverse the BST every time peek() is called

D. Use a stack to store left children and keep the top as peek value

Solution

1. Step 1: Understand peek() requirement

   peek() must return next smallest element without moving forward, so the next element must be accessible without popping.

2. Step 2: Evaluate approaches

   Use a stack to store left children and keep the top as peek value uses a stack with left children; the top of the stack is the next smallest element, so peek() can return it efficiently. Store all BST elements in an array and use an index pointer stores all elements but uses extra memory. Traverse the BST every time peek() is called is inefficient as it traverses repeatedly. Use a queue to store nodes in BFS order uses BFS order, which is not sorted.

3. Final Answer:

   Use a stack to store left children and keep the top as peek value -> Option D

4. Quick Check:

   Stack top = next smallest for peek() [OK]

Hint: Stack top always holds next smallest for peek() [OK]

Common Mistakes:

• Using BFS queue which is unordered
• Re-traversing tree on every peek() call
• Storing all elements wastes memory