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.

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 storing all elements at once

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 loading all nodes into memory at once.

2. Step 2: Compare options with BST Iterator purpose

   Options B, C, and D relate to modifying the tree, not iterating over it. To traverse the BST in ascending order without storing all elements at once correctly describes the iterator's purpose.

3. Final Answer:

   To traverse the BST in ascending order without storing all elements at once -> Option A

4. Quick Check:

   BST Iterator = In-order traversal on demand [OK]

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

Common Mistakes:

• Confusing iterator with insertion or deletion operations
• Thinking iterator balances the tree
• Assuming iterator stores all nodes at once

2. Which of the following is the correct TypeScript method signature for the next() method in a BST Iterator class that returns the next smallest number?

easy

A. next(value: number): number

B. next(): void

C. next(): number

D. next(): boolean

Solution

1. Step 1: Understand the purpose of next()

   The next() method should return the next smallest number in the BST, so it must return a number.

2. Step 2: Analyze method signatures

   next(): number returns a number with no parameters, which fits the iterator pattern. next(): void returns void, so no value is returned. next(value: number): number takes a parameter, which is not needed. next(): boolean returns boolean, which is incorrect.

3. Final Answer:

   next(): number -> Option C

4. Quick Check:

   next() returns next smallest number [OK]

Hint: next() returns a number without parameters [OK]

Common Mistakes:

• Adding unnecessary parameters to next()
• Returning void instead of number
• Returning boolean instead of number

3. Given the following BST Iterator usage in TypeScript, what will be the output printed?

const root = {
  val: 7,
  left: { val: 3, left: null, right: null },
  right: { val: 15, left: { val: 9, left: null, right: null }, right: { val: 20, left: null, right: null } }
};

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

medium

A. [3, 7, true, 9]

B. [7, 3, true, 9]

C. [3, 7, false, 9]

D. [3, 9, true, 15]

Solution

1. Step 1: Understand BST in-order traversal order

   The BST nodes in ascending order are 3, 7, 9, 15, 20.

2. Step 2: Trace iterator calls

   First next() returns 3, second next() returns 7, hasNext() returns true because more nodes exist, third next() returns 9.

3. Final Answer:

   [3, 7, true, 9] -> Option A

4. Quick Check:

   In-order traversal = 3,7,9,... [OK]

Hint: Remember BST in-order is sorted ascending [OK]

Common Mistakes:

• Mixing up left and right subtree order
• Assuming hasNext() returns next value
• Confusing node values order

4. Consider this partial TypeScript BST Iterator class code. What is the bug?

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

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

  pushLeft(node: TreeNode | null) {
    while (node !== null) {
      this.stack.push(node);
      node = node.right;  // Bug here
    }
  }

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

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

medium

A. next() should pop from the front, not the end

B. In pushLeft, should traverse left child, not right

C. hasNext() should check if stack is empty incorrectly

D. Constructor should not call pushLeft

Solution

1. Step 1: Analyze pushLeft method

   pushLeft should push all left children to stack to simulate in-order traversal. The code incorrectly moves to node.right instead of node.left.

2. Step 2: Check other methods

   next() correctly pops from stack and pushes left children of right subtree. hasNext() correctly checks stack length. Constructor correctly calls pushLeft.

3. Final Answer:

   In pushLeft, should traverse left child, not right -> Option B

4. Quick Check:

   pushLeft must go left to simulate in-order [OK]

Hint: pushLeft must follow left children, not right [OK]

Common Mistakes:

• Traversing right child in pushLeft instead of left
• Misunderstanding stack usage in iterator
• Incorrect pop direction in next()

5. You want to design a BST Iterator that supports peek() to see the next smallest element without advancing the iterator. Which approach best supports this feature efficiently?

hard

A. Use a queue to store nodes in BFS order

B. Store all BST elements in an array and use an index pointer

C. Traverse the BST every time peek() is called

D. Use a stack to store left children and keep the top as peek value

Solution

1. Step 1: Understand peek() requirement

   peek() must return next smallest element without moving forward, so the next element must be accessible without popping.

2. Step 2: Evaluate approaches

   Use a stack to store left children and keep the top as peek value uses a stack with left children; the top of the stack is the next smallest element, so peek() can return it efficiently. Store all BST elements in an array and use an index pointer stores all elements but uses extra memory. Traverse the BST every time peek() is called is inefficient as it traverses repeatedly. Use a queue to store nodes in BFS order uses BFS order, which is not sorted.

3. Final Answer:

   Use a stack to store left children and keep the top as peek value -> Option D

4. Quick Check:

   Stack top = next smallest for peek() [OK]

Hint: Stack top always holds next smallest for peek() [OK]

Common Mistakes:

• Using BFS queue which is unordered
• Re-traversing tree on every peek() call
• Storing all elements wastes memory