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.