BST Iterator Design in DSA Go - 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 sorted order without loading them all at once. This is like flipping through pages of a book, seeing one page at a time.

🎯 Goal: You will build a BSTIterator in Go that lets you move through the BST in order, one number at a time. This iterator 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 BST node structure called TreeNode with Val, Left, and Right fields

Create a BSTIterator struct with a stack to help traverse the tree

Implement a constructor function Constructor(root *TreeNode) BSTIterator to initialize the iterator

Implement Next() int method to return the next smallest number

Implement HasNext() bool method to check if more numbers are available

Use a stack to simulate the in-order traversal without recursion

💡 Why This Matters

🌍 Real World

BST iterators are used in databases and search engines to efficiently access sorted data without loading everything at once.

💼 Career

Understanding BST iterators helps in roles involving data structure optimization, backend development, and systems programming.

1

Create the BST Node Structure

Create a struct called TreeNode with three fields: Val int, Left *TreeNode, and Right *TreeNode.

DSA Go

// Your code here

Hint

Think of TreeNode as a box holding a number and links to two other boxes (left and right).

2

Set Up the BSTIterator Structure and Constructor

Create a struct called BSTIterator with a field stack of type []*TreeNode. Then write a function Constructor(root *TreeNode) BSTIterator that initializes the stack and pushes all left children of root onto the stack.

DSA Go

type BSTIterator struct {
    stack []*TreeNode
}

func Constructor(root *TreeNode) BSTIterator {
    it := BSTIterator{stack: []*TreeNode{}}
    // Your code here
    return it
}

Hint

Use a loop to go left down the tree and push nodes onto the stack.

3

Implement Next() and HasNext() Methods

Add a method Next() int to BSTIterator that pops the top node from the stack, pushes all left children of its right child, and returns its value. Also add a method HasNext() bool that returns true if the stack is not empty.

DSA Go

func (this *BSTIterator) Next() int {
    // Your code here
}

func (this *BSTIterator) HasNext() bool {
    // Your code here
}

Hint

Pop the top node, then push all left children of its right child to the stack.

4

Test the BSTIterator by Printing All Values in Order

Create a sample BST with root node value 7, left child 3, and right child 15 with children 9 and 20. Initialize BSTIterator with this root. Use a for loop with HasNext() and Next() to print all values in sorted order separated by spaces.

DSA Go

func main() {
    // Your code here
}

Hint

Build the tree exactly as described and use a loop to print values with spaces.