BST Iterator Design in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

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

DSA Typescript

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

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

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

Apush

Bpop

Cshift

Dunshift

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop instead of push

Using shift or unshift which are queue operations

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

2fill in blank

medium

Complete the code to check if the iterator has a next smallest number.

DSA Typescript

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

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

Asize

Bcount

Clength

Dcapacity

Attempts:

3 left

💡 Hint

Common Mistakes

Using size which is for sets or maps

Using count or capacity which are not valid array properties

The length property gives the number of elements in the array (stack).

3fill in blank

hard

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

DSA Typescript

next(): number {
  const topmostNodeVal = this.stack.[1]();
  return topmostNodeVal!.val;
}

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

Apush

Bpop

Cshift

Dunshift

Attempts:

3 left

💡 Hint

Common Mistakes

Using push which adds instead of removes

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

We use pop to remove and return the top element from the stack.

4fill in blank

hard

Fill both blanks to add the right child nodes to the stack after popping the top node.

DSA Typescript

next(): number {
  const topmostNodeVal = this.stack.pop();
  if (topmostNodeVal !== undefined) {
    let node = topmostNodeVal.[1];
    while (node !== null) {
      this.stack.[2](node);
      node = node.left;
    }
  }
  return topmostNodeVal!.val;
}

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

Aright

Bleft

Cpush

Dpop

Attempts:

3 left

💡 Hint

Common Mistakes

Using left instead of right for the child

Using pop instead of push to add nodes

After popping, we move to the right child and push its left descendants.

5fill in blank

hard

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

DSA Typescript

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

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

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

  hasNext(): boolean {
    return this.stack.[2] > 0;
  }

  next(): number {
    const topmostNode = this.stack.[3]();
    if (topmostNode.right !== null) {
      this._leftmostInorder(topmostNode.right);
    }
    return topmostNode.val;
  }
}

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

Apush

Bpop

Clength

Dsize

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop instead of push in _leftmostInorder

Using size instead of length for array

Using push instead of pop in next

Push nodes in _leftmostInorder, check stack length in hasNext, pop nodes in next.