BST Iterator Design in DSA Javascript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the stack in the BST Iterator constructor.

DSA Javascript

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

  _leftmostInorder(node) {
    while (node !== null) {
      this.stack.[1](node);
      node = node.left;
    }
  }
}

Drag options to blanks, or click blank then click option'

Aunshift

Bpop

Cshift

Dpush

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'pop' instead of 'push' which removes elements instead of adding.

Using 'shift' or 'unshift' which operate on the start of the array, not the end.

We use 'push' to add nodes to the stack as we traverse left.

2fill in blank

medium

Complete the code to check if there is a next smallest number in the BST Iterator.

DSA Javascript

hasNext() {
  return this.stack.[1] > 0;
}

Drag options to blanks, or click blank then click option'

Alength()

Blength

Ccount

Dsize

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'size' which is for Sets or Maps, not arrays.

Using 'length()' as a function which causes an error.

'length' is the property to get the number of elements in an array in JavaScript.

3fill in blank

hard

Fix the error in the next() method to correctly return the next smallest number.

DSA Javascript

next() {
  let topNode = this.stack.[1]();
  if (topNode.right !== null) {
    this._leftmostInorder(topNode.right);
  }
  return topNode.val;
}

Drag options to blanks, or click blank then click option'

Apop

Bpush

Cshift

Dunshift

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'push' which adds instead of removing.

Using 'shift' or 'unshift' which operate on the start of the array.

'pop' removes and returns the last element from the stack, which is the next smallest node.

4fill in blank

hard

Fill both blanks to complete the _leftmostInorder helper method that pushes nodes onto the stack while traversing left.

DSA Javascript

_leftmostInorder(node) {
  while (node !== null) {
    this.stack.[1](node);
    node = node.[2];
  }
}

Drag options to blanks, or click blank then click option'

Apush

Bpop

Cleft

Dright

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'pop' instead of 'push' to add nodes.

Moving to 'right' child instead of 'left' in this helper.

We push the current node and move to its left child to traverse the leftmost path.

5fill in blank

hard

Fill all three blanks to complete the BST Iterator class with constructor, hasNext, and next methods.

DSA Javascript

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

  _leftmostInorder(node) {
    while (node !== null) {
      this.stack.[2](node);
      node = node.left;
    }
  }

  hasNext() {
    return this.stack.[3] > 0;
  }

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

Drag options to blanks, or click blank then click option'

Aroot

Bpush

Clength

Dpop

Attempts:

3 left

💡 Hint

Common Mistakes

Calling _leftmostInorder with wrong argument.

Using 'pop' instead of 'push' in _leftmostInorder.

Using 'size' or 'length()' instead of 'length' in hasNext.

The constructor calls _leftmostInorder with 'root', _leftmostInorder pushes nodes, and hasNext checks stack length.