Why BST Iterator Design in DSA Go?

The Big Idea

Discover how a simple iterator can turn a confusing tree into a smooth, step-by-step journey!

The Scenario

Imagine you have a large family tree drawn on paper, and you want to look at each member one by one in order from youngest to oldest. Doing this manually means flipping back and forth through the pages, trying to remember where you left off.

The Problem

Manually tracking where you are in the family tree is slow and confusing. You might lose your place, repeat members, or skip some. It's hard to keep the order right without a clear system.

The Solution

A BST Iterator acts like a smart bookmark that remembers exactly where you are in the tree. It lets you move step-by-step in order, without losing track or needing to start over.

Before vs After

✗ Before

func inorderTraversal(root *TreeNode) []int {
    var result []int
    var stack []*TreeNode
    current := root
    for current != nil || len(stack) > 0 {
        for current != nil {
            stack = append(stack, current)
            current = current.Left
        }
        current = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        result = append(result, current.Val)
        current = current.Right
    }
    return result
}

✓ After

type BSTIterator struct {
    stack []*TreeNode
}

func Constructor(root *TreeNode) BSTIterator {
    iterator := BSTIterator{stack: []*TreeNode{}}
    iterator.pushLeft(root)
    return iterator
}

func (it *BSTIterator) pushLeft(node *TreeNode) {
    for node != nil {
        it.stack = append(it.stack, node)
        node = node.Left
    }
}

func (it *BSTIterator) Next() int {
    node := it.stack[len(it.stack)-1]
    it.stack = it.stack[:len(it.stack)-1]
    it.pushLeft(node.Right)
    return node.Val
}

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

What It Enables

This design lets you explore a binary search tree step-by-step in order, efficiently and without extra memory for the whole tree.

Real Life Example

Think of browsing a sorted list of contacts on your phone. The BST Iterator helps you move from one contact to the next in alphabetical order without loading all contacts at once.

Key Takeaways

Manual tree traversal is hard to pause and resume.

BST Iterator remembers your place and moves in order.

It uses a stack to track nodes efficiently.

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