BST Iterator Design in DSA Typescript - Build from Scratch

BST Iterator Design

📖 Scenario: Imagine you have a large collection of numbers stored in a Binary Search Tree (BST). You want to look at these numbers one by one in ascending order, like flipping through pages of a book. To do this efficiently, you will build a special tool called a BST Iterator that helps you see the next smallest number each time you ask for it.

🎯 Goal: You will create a BSTIterator class in TypeScript that lets you move through the BST in order. It will have two main actions: next() to get the next smallest number, and hasNext() to check if there are more numbers to see.

📋 What You'll Learn

Create a TreeNode class to represent nodes in the BST with val, left, and right properties.

Create a BSTIterator class with a constructor that takes the root of the BST.

Implement a private stack inside BSTIterator to help with in-order traversal.

Implement hasNext() method to check if there are more nodes to visit.

Implement next() method to return the next smallest value in the BST.

💡 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 into memory.

💼 Career

Understanding BST iterators helps in roles involving data structure optimization, algorithm design, and backend development where efficient data traversal is critical.

1

Create the TreeNode class

Create a TypeScript class called TreeNode with a constructor that takes a number val, and optional left and right nodes of type TreeNode | null. Initialize the properties val, left, and right inside the constructor.

DSA Typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;

  constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
    // Your code here
  }
}

Hint

Remember to assign the constructor parameters to the class properties using this.

2

Initialize the BSTIterator with a stack

Create a TypeScript class called BSTIterator with a private property stack of type TreeNode[]. Add a constructor that takes a root of type TreeNode | null and initializes the stack as an empty array. Then call a private method pushLeftNodes with the root to prepare the stack.

DSA Typescript

class BSTIterator {
  private stack: TreeNode[];

  constructor(root: TreeNode | null) {
    // Your code here
  }

  private pushLeftNodes(node: TreeNode | null): void {
    // Your code here
  }
}

Hint

Use a while loop to push all left children of the node onto the stack.

3

Implement hasNext() and next() methods

Inside the BSTIterator class, implement the method hasNext() that returns true if the stack is not empty, otherwise false. Also implement the method next() that pops the top node from the stack, calls pushLeftNodes on its right child, and returns the popped node's val.

DSA Typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;

  constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

class BSTIterator {
  private stack: TreeNode[];

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

  private pushLeftNodes(node: TreeNode | null): void {
    while (node !== null) {
      this.stack.push(node);
      node = node.left;
    }
  }

  hasNext(): boolean {
    // Your code here
  }

  next(): number {
    // Your code here
  }
}

Hint

Use this.stack.length > 0 to check if there are more nodes. In next(), pop from the stack, then push left nodes of the popped node's right child.

4

Test the BSTIterator output

Create a BST with root node value 7, left child 3, and right child 15. The right child 15 has two children: left 9 and right 20. Create a BSTIterator instance with this root. Then, print the results of calling next(), next(), hasNext(), next(), hasNext(), next(), hasNext(), and next() in this order, each on its own line.

DSA Typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;

  constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

class BSTIterator {
  private stack: TreeNode[];

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

  private pushLeftNodes(node: TreeNode | null): void {
    while (node !== null) {
      this.stack.push(node);
      node = node.left;
    }
  }

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

  next(): number {
    const node = this.stack.pop()!;
    this.pushLeftNodes(node.right);
    return node.val;
  }
}

// Your code here

Hint

Build the tree exactly as described. Call the methods in the given order and print their results.