0
0
DSA Typescriptprogramming~20 mins

BST Iterator Design in DSA Typescript - Practice Problems & Challenges

Choose your learning style9 modes available
LearnWhyDeepVisualTryChallengeProjectRecallTime
Challenge - 5 Problems
🎖️
BST Iterator Master
Get all challenges correct to earn this badge!
Test your skills under time pressure!
❓ Predict Output
intermediate
2:00remaining
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]
Attempts:
2 left
💡 Hint
Remember that BST Iterator returns nodes in ascending order using in-order traversal.
🧠 Conceptual
intermediate
1:00remaining
Understanding BST Iterator hasNext() behavior
What does the hasNext() method of a BST Iterator indicate during iteration?
AIt returns true if there are still nodes left to visit in ascending order.
BIt returns true if the current node has a right child.
CIt returns true if the BST is balanced.
DIt returns true if the stack is empty.
Attempts:
2 left
💡 Hint
Think about what the stack in the iterator represents.
🔧 Debug
advanced
1:30remaining
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;
}
ASyntaxError due to missing semicolon
BReferenceError because pushLeft is not defined
CNo error, code runs correctly
DTypeError because node can be undefined if stack is empty
Attempts:
2 left
💡 Hint
What happens if stack.pop() returns undefined?
❓ Predict Output
advanced
2:00remaining
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]
Attempts:
2 left
💡 Hint
Check the in-order traversal sequence and test evenness of each value.
🧠 Conceptual
expert
1:00remaining
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?
AO(log n), where n is the number of nodes in the BST
BO(n), where n is the number of nodes in the BST
CO(h), where h is the height of the BST
DO(1), constant space
Attempts:
2 left
💡 Hint
Consider the maximum number of nodes stored in the stack at once.