BST Iterator Design in DSA Javascript - Build from Scratch

BST Iterator Design

📖 Scenario: You are building a tool to explore a collection of numbers stored in a special tree called a Binary Search Tree (BST). This tree keeps numbers in order, so you can find the smallest number quickly. You want to create a helper called a BST Iterator that lets you look at the numbers one by one, from smallest to largest, without changing the tree.

🎯 Goal: Build a BST Iterator that can move through the tree in order, showing one number at a time. You will create the tree, set up the iterator, write the logic to get the next number, and finally print the numbers in order.

📋 What You'll Learn

Create a BST with the exact nodes given

Create a stack to help with the iterator

Write a function to move to the next smallest number

Print the numbers in ascending order using the iterator

💡 Why This Matters

🌍 Real World

BST Iterators are useful in databases and search engines where you need to access sorted data efficiently without loading everything at once.

💼 Career

Understanding BST Iterators helps in roles involving data structures, algorithms, and system design, especially for optimizing search and retrieval operations.

1

Create the BST nodes

Create a BST with nodes exactly as follows: root node with value 7, left child with value 3, right child with value 15, and the right child of 15 has two children with values 9 (left) and 20 (right). Use the class TreeNode with properties val, left, and right. Create a variable called root for the root node.

DSA Javascript

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

// Create the BST nodes and assign to root
// Your code here

Hint

Start by creating the root node with value 7. Then add left and right children as described. Use new TreeNode(value, left, right) to create nodes.

2

Set up the BST Iterator class with a stack

Create a class called BSTIterator with a constructor that takes the root node. Inside the constructor, create a property called stack initialized as an empty array. Also, write a helper method called _leftmostInorder that takes a node and pushes all its left children onto the stack. Call _leftmostInorder(root) inside the constructor.

DSA Javascript

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

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

class BSTIterator {
  constructor(root) {
    // Your code here
  }

  _leftmostInorder(node) {
    // Your code here
  }
}

Hint

Initialize stack as an empty array. Use a while loop to push all left nodes starting from the given node.

3

Add the next() and hasNext() methods

Inside the BSTIterator class, add a method called next() that removes the top node from stack, saves its value, then calls _leftmostInorder on the right child of that node. Return the saved value. Also add a method called hasNext() that returns true if stack is not empty, otherwise false.

DSA Javascript

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

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

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

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

  next() {
    // Your code here
  }

  hasNext() {
    // Your code here
  }
}

Hint

In next(), pop from stack, call _leftmostInorder on right child, and return the popped node's value. In hasNext(), check if stack is not empty.

4

Use the BST Iterator to print all values in order

Create an instance of BSTIterator called iterator using the root. Use a while loop that runs as long as iterator.hasNext() is true. Inside the loop, print the result of iterator.next() separated by spaces on one line.

DSA Javascript

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

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

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();
    this._leftmostInorder(topNode.right);
    return topNode.val;
  }

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

const iterator = new BSTIterator(root);

// Print all values in order separated by spaces
// Your code here

Hint

Create the iterator, then use a while loop to get each next value and add it to a string. Print the string after the loop.

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 recursion

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 using recursion.

2. Step 2: Identify the main purpose

   It provides a way to get the next smallest element efficiently, which matches To traverse the BST in ascending order without recursion.

3. Final Answer:

   To traverse the BST in ascending order without recursion -> Option A

4. Quick Check:

   BST Iterator = Ascending traversal without recursion [OK]

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

Common Mistakes:

• Confusing iterator with insertion or deletion
• Thinking it balances the tree automatically
• Assuming it uses recursion internally

2. Which of the following is the correct way to initialize a BST Iterator class in JavaScript?

easy

A. function BSTIterator(root) { this.stack = []; this.pushRight(root); }

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

C. class BSTIterator { constructor(root) { this.queue = []; this.pushLeft(root); } }

D. function BSTIterator(root) { this.queue = []; this.pushRight(root); }

Solution

1. Step 1: Identify correct class syntax and initialization

   The BST Iterator is usually implemented as a class with a stack to store nodes and a helper method to push left children.

2. Step 2: Check each option

   class BSTIterator { constructor(root) { this.stack = []; this.pushLeft(root); } } correctly uses a class, initializes a stack, and calls pushLeft on root. Others use queue or pushRight which are incorrect for BST Iterator.

3. Final Answer:

   class BSTIterator { constructor(root) { this.stack = []; this.pushLeft(root); } } -> Option B

4. Quick Check:

   Use stack and pushLeft in constructor [OK]

Hint: BST Iterator uses stack and pushLeft method [OK]

Common Mistakes:

• Using queue instead of stack
• Calling pushRight instead of pushLeft
• Using function instead of class syntax

3. Given the BST below and the following code snippet, what will be the output? BST structure: ``` 7 / \ 3 15 / \ 9 20 ``` Code:

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

medium

A. [3, 7, false]

B. [7, 9, true]

C. [3, 7, true]

D. [9, 15, true]

Solution

1. Step 1: Trace the first next() call

   First next() returns the smallest element, which is 3.

2. Step 2: Trace the second next() call

   Second next() returns the next smallest, which is 7.

3. Step 3: Check hasNext()

   After two next() calls, there are still nodes (9, 15, 20), so hasNext() returns true.

4. Final Answer:

   [3, 7, true] -> Option C

5. Quick Check:

   next() returns ascending nodes, hasNext() true if more nodes [OK]

Hint: next() returns next smallest; hasNext() true if stack not empty [OK]

Common Mistakes:

• Assuming next() returns root first
• Confusing hasNext() return value
• Ignoring left subtree nodes

4. Consider this buggy BST Iterator method. What is the main error?

next() {
  const node = this.stack.pop();
  if (node.right) {
    this.pushRight(node.right);
  }
  return node.val;
}

pushRight(node) {
  while (node) {
    this.stack.push(node);
    node = node.right;
  }
}

medium

A. next() should not pop from stack

B. next() should return node.key instead of node.val

C. pushRight should use a queue instead of stack

D. pushRight should push left children, not right

Solution

1. Step 1: Analyze pushRight method

   pushRight pushes right children, but BST Iterator needs to push left children to get next smallest.

2. Step 2: Understand correct pushLeft usage

   Correct method pushes left children of right subtree to stack to maintain ascending order.

3. Final Answer:

   pushRight should push left children, not right -> Option D

4. Quick Check:

   Push left children to stack for correct order [OK]

Hint: Push left children of right subtree, not right children [OK]

Common Mistakes:

• Pushing right children instead of left
• Using queue instead of stack
• Returning wrong node property

5. You want to design a BST Iterator that supports next() and hasNext() in O(1) average time and uses O(h) space, where h is tree height. Which approach best achieves this?

hard

A. Use a stack to store left children and push left nodes of right subtree on next()

B. Store all nodes in an array by inorder traversal at initialization

C. Use recursion to traverse nodes on each next() call

D. Use a queue to store nodes level by level

Solution

1. Step 1: Understand time and space constraints

   O(1) average time per next() and O(h) space means no full traversal storage and no recursion per call.

2. Step 2: Evaluate each approach

   Use a stack to store left children and push left nodes of right subtree on next() uses a stack to store left children and pushes left nodes of right subtree on next(), achieving O(1) average time and O(h) space. Store all nodes in an array by inorder traversal at initialization uses O(n) space. Use recursion to traverse nodes on each next() call uses recursion, not O(1) time. Use a queue to store nodes level by level uses queue level order, not inorder.

3. Final Answer:

   Use a stack to store left children and push left nodes of right subtree on next() -> Option A

4. Quick Check:

   Stack + push left children = O(1) avg time, O(h) space [OK]

Hint: Use stack with left children for efficient BST Iterator [OK]

Common Mistakes:

• Storing all nodes wastes space
• Using recursion causes slow next()
• Using queue gives wrong traversal order