BST Iterator Design in DSA C++ - Build from Scratch

BST Iterator Design

📖 Scenario: Imagine you have a large collection of numbers stored in a special tree called a Binary Search Tree (BST). You want to look at these numbers one by one in order, like flipping through pages in a book. To do this easily, you will build a tool called a BST Iterator that helps you move through the numbers step-by-step.

🎯 Goal: You will create a BST Iterator in C++ that lets you go through the numbers in the tree from smallest to largest. You will build it step-by-step: first creating the tree, then setting up the iterator, then writing the main logic to move through the tree, and finally printing the numbers in order.

📋 What You'll Learn

Create a BST with given nodes

Implement a stack to help with the iterator

Write the iterator methods to get 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 structure optimization, system design, and coding interviews.

1

Create the BST nodes

Create a struct called TreeNode with an int val, and two pointers left and right. Then create the BST with these exact nodes and connections:
root with value 7,
root's left child with value 3,
root's right child with value 15,
15's left child with value 9,
15's right child with value 20.

DSA C++

// Define TreeNode struct and create the BST nodes
// Your code here

Hint

Start by defining the TreeNode structure with value and pointers. Then create each node and connect them exactly as described.

2

Set up the BST Iterator class with a stack

Create a class called BSTIterator with a private member std::stack called nodeStack. Add a constructor that takes a TreeNode* called root and calls a private method pushLeft(TreeNode* node) to push all left children of root onto nodeStack.

DSA C++

class BSTIterator {
private:
    std::stack nodeStack;
    void pushLeft(TreeNode* node);
public:
    BSTIterator(TreeNode* root);
    // Your code here
};

Hint

Use a stack to store nodes. The constructor should call pushLeft to add all left nodes starting from root.

3

Implement next() and hasNext() methods

Inside the BSTIterator class, implement the method int next() that pops the top node from nodeStack, calls pushLeft on its right child, and returns its value. Also implement bool hasNext() that returns true if nodeStack is not empty, otherwise false.

DSA C++

class BSTIterator {
private:
    std::stack nodeStack;
    void pushLeft(TreeNode* node) {
        while (node != nullptr) {
            nodeStack.push(node);
            node = node->left;
        }
    }
public:
    BSTIterator(TreeNode* root) {
        pushLeft(root);
    }
    int next();
    bool hasNext();
    // Your code here
};

Hint

Use next() to pop the top node, push left nodes of its right child, and return its value. hasNext() checks if stack is empty.

4

Use the BST Iterator to print all values in ascending order

Create a BSTIterator object called iterator with root. Use a while loop with iterator.hasNext() to print each value returned by iterator.next() separated by spaces.

DSA C++

BSTIterator iterator(root);
// Use while loop to print values in ascending order
// Your code here

Hint

Create the iterator and use a loop to print all values in order separated by spaces.