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.

Practice

1. What is the main purpose of a BST Iterator in a binary search tree?

easy

A. To balance the BST automatically

B. To insert new nodes into the BST

C. To traverse the BST in ascending order without recursion

D. To delete nodes from the BST

Solution

1. Step 1: Understand BST Iterator functionality

   A BST Iterator is designed to traverse the tree in sorted order, typically ascending, without using recursion explicitly.

2. Step 2: Identify the main purpose

   It provides a way to get the next smallest element efficiently, which matches To traverse the BST in ascending order without recursion.

3. Final Answer:

   To traverse the BST in ascending order without recursion -> Option C

4. Quick Check:

   BST Iterator = In-order traversal without recursion [OK]

Hint: BST Iterator returns next smallest element in order [OK]

Common Mistakes:

• Confusing iterator with insertion or deletion
• Thinking it balances the tree automatically
• Assuming it uses recursion internally

2. Which of the following is the correct method signature for the Next() function in a BST Iterator in Go?

easy

A. func (it *BSTIterator) Next() int

B. func Next(it BSTIterator) int

C. func (it BSTIterator) Next() int

D. func Next() int

Solution

1. Step 1: Understand method receiver in Go

   Methods with pointer receivers allow modifying the iterator's internal state, which is needed for Next().

2. Step 2: Identify correct signature

   func (it *BSTIterator) Next() int uses pointer receiver *BSTIterator and returns an int, matching the expected signature.

3. Final Answer:

   func (it *BSTIterator) Next() int -> Option A

4. Quick Check:

   Pointer receiver + return int = func (it *BSTIterator) Next() int [OK]

Hint: Use pointer receiver to update iterator state [OK]

Common Mistakes:

• Using value receiver which copies state
• Defining Next as a standalone function
• Omitting receiver entirely

3. Given the BST with nodes 7, 3, 15, 9, 20 inserted in that order, what will be the output of calling Next() three times on a correctly implemented BST Iterator?

medium

A. [3, 7, 9]

B. [7, 9, 15]

C. [3, 9, 15]

D. [7, 3, 9]

Solution

1. Step 1: Build BST and find in-order traversal

   Inserting 7, 3, 15, 9, 20 creates BST with in-order: 3, 7, 9, 15, 20.

2. Step 2: Identify first three Next() outputs

   Calling Next() three times returns first three smallest elements: 3, 7, 9.

3. Final Answer:

   [3, 7, 9] -> Option A

4. Quick Check:

   In-order first 3 = [3,7,9] [OK]

Hint: Next() returns next smallest in sorted order [OK]

Common Mistakes:

• Confusing insertion order with traversal order
• Mixing up left and right child positions
• Assuming Next() returns inserted order

4. Consider this buggy Go code snippet for BST Iterator's HasNext() method:

func (it *BSTIterator) HasNext() bool {
    return len(it.stack) > 0
}

What is the main issue if the stack is not properly initialized during iterator creation?

medium

A. HasNext() incorrectly modifies the stack contents

B. HasNext() will cause a runtime panic due to nil slice access

C. HasNext() always returns true regardless of stack state

D. HasNext() may return false even if nodes remain unvisited

Solution

1. Step 1: Understand stack role in BST Iterator

   The stack holds nodes to visit; if not initialized, it may be empty even if tree has nodes.

2. Step 2: Analyze HasNext() behavior

   HasNext() checks stack length; if stack is empty due to no initialization, it returns false prematurely.

3. Final Answer:

   HasNext() may return false even if nodes remain unvisited -> Option D

4. Quick Check:

   Uninitialized stack = false HasNext() early [OK]

Hint: Initialize stack with leftmost nodes before HasNext() [OK]

Common Mistakes:

• Assuming nil slice causes panic on len()
• Expecting HasNext() to modify stack
• Ignoring stack initialization in constructor

5. You want to design a BST Iterator that supports Next() and HasNext() with O(1) average time and O(h) space, where h is tree height. Which approach best achieves this?

hard

A. Store all nodes in a slice during initialization and iterate over it

B. Use a stack to store leftmost nodes and push right child nodes lazily during Next()

C. Use recursion to traverse nodes on each Next() call

D. Use a queue to store nodes in level order and dequeue on Next()

Solution

1. Step 1: Analyze time and space constraints

   O(1) average time per Next() and O(h) space means no full traversal upfront.

2. Step 2: Evaluate approaches

   Use a stack to store leftmost nodes and push right child nodes lazily during Next() uses a stack with lazy pushing of right children, matching constraints efficiently.

3. Step 3: Reject other options

   Store all nodes in a slice during initialization and iterate over it uses O(n) space, C uses recursion (not O(1) average), D uses queue with level order, not sorted order.

4. Final Answer:

   Use a stack to store leftmost nodes and push right child nodes lazily during Next() -> Option B

5. Quick Check:

   Stack + lazy push = O(1) avg time, O(h) space [OK]

Hint: Use stack with lazy right child push for efficient iteration [OK]

Common Mistakes:

• Preloading all nodes wastes space
• Using recursion breaks O(1) average time
• Using queue breaks sorted order iteration