BST Iterator Design in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of BST Iterator next() calls

Given the BST Iterator initialized with the BST below, what is the output sequence of calling next() three times?

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._leftmostInorder(root);
  }

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

  next() {
    const topNode = this.stack.pop();
    if (topNode.right !== null) {
      this._leftmostInorder(topNode.right);
    }
    return topNode.val;
  }

  hasNext() {
    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 = [iterator.next(), iterator.next(), iterator.next()];
console.log(output);

A [3, 7, 9]

B [7, 3, 9]

C [3, 9, 7]

D [7, 9, 15]

💡 Hint

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

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

🧠 Conceptual

intermediate

Understanding BST Iterator hasNext() behavior

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

A It returns true if the stack is empty.

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

C It returns true if there are more nodes to visit in ascending order.

D It returns true if the BST is balanced.

💡 Hint

Think about what the stack in the iterator represents.

hasNext() returns true if the stack is not empty, meaning there are still nodes left to visit in ascending order.

🔧 Debug

advanced

Identify the error in BST Iterator next() method

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

DSA Javascript

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

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

  next() {
    const topNode = this.stack.pop();
    if (topNode.right !== null) {
      this._leftmostInorder(topNode.right);
    }
    return topNode.val;
  }

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

const iterator = new BSTIterator(null);
iterator.next();

A No error, returns null

B TypeError: Cannot read property 'right' of undefined

C ReferenceError: topNode is not defined

D RangeError: Maximum call stack size exceeded

💡 Hint

Consider what happens when the BST is empty and next() is called.

When the BST is empty, the stack is empty, so pop() returns undefined. Accessing topNode.right causes a TypeError.

🚀 Application

advanced

Number of next() calls to traverse entire BST

If a BST Iterator is initialized with a BST of 10 nodes, how many times must next() be called to visit all nodes?

A 10

B 9

C 11

D Depends on the shape of the BST

💡 Hint

Each next() call returns one node's value.

Each next() call returns exactly one node in ascending order, so to visit all 10 nodes, next() must be called 10 times.

🧠 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(1), constant space

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

C O(log n), assuming the BST is balanced

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

💡 Hint

Consider how many nodes can be on the stack at once during traversal.

The stack stores nodes along the path from root to the current node, which is at most the height h of the BST.