BST Iterator Design in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of BST Iterator Next Calls

Given a BST with nodes inserted in this order: 7, 3, 15, 9, 20, what is the output of calling Next() three times on a BST iterator initialized with this tree?

DSA Go

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

type BSTIterator struct {
    stack []*TreeNode
}

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

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

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

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

// Tree construction
root := &TreeNode{7, nil, nil}
root.Left = &TreeNode{3, nil, nil}
root.Right = &TreeNode{15, nil, nil}
root.Right.Left = &TreeNode{9, nil, nil}
root.Right.Right = &TreeNode{20, nil, nil}

it := Constructor(root)
output := []int{it.Next(), it.Next(), it.Next()}
fmt.Println(output)

A [3, 7, 9]

B [7, 3, 9]

C [7, 9, 15]

D [3, 9, 7]

💡 Hint

Remember, BST Iterator returns nodes in ascending order (inorder traversal).

The BST iterator uses a stack to traverse the tree in ascending order. The first Next() returns the smallest element 3, then 7, then 9.

🧠 Conceptual

intermediate

BST Iterator Space Complexity

What is the maximum space used by a BST Iterator implemented with a stack for a BST with n nodes?

A O(n), because in the worst case the stack holds all nodes in the tree

B O(log n), because the stack holds nodes along one path from root to leaf

C O(1), because the iterator uses constant extra space

D O(n log n), because the stack stores nodes for each level

💡 Hint

Think about the maximum height of the stack during traversal.

The stack stores nodes along the path from root to the current node, which is at most the height of the tree. For a balanced BST, height is O(log n).

🔧 Debug

advanced

Identify the Bug in BST Iterator Next Method

What error will this BST Iterator Next() method cause when called on a non-empty iterator?

DSA Go

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

A runtime error: nil pointer dereference

B returns the correct next value

C compilation error due to missing return type

D runtime error: index out of range

💡 Hint

Check how the stack index is accessed.

The code accesses this.stack[len(this.stack)] which is out of range because slice indices go from 0 to len-1.

❓ Predict Output

advanced

BST Iterator HasNext Behavior

Given a BST iterator initialized with a tree containing nodes 5, 3, 7, what is the output of calling HasNext() four times after three Next() calls?

DSA Go

root := &TreeNode{5, nil, nil}
root.Left = &TreeNode{3, nil, nil}
root.Right = &TreeNode{7, nil, nil}

it := Constructor(root)

results := []bool{}
results = append(results, it.HasNext())
results = append(results, it.Next() == 3)
results = append(results, it.HasNext())
results = append(results, it.Next() == 5)
results = append(results, it.HasNext())
results = append(results, it.Next() == 7)
results = append(results, it.HasNext())
fmt.Println(results)

A [true, true, true, true, false, true, false]

B [true, true, true, true, true, false, false]

C [true, true, true, true, true, true, false]

D [true, true, false, true, true, true, false]

💡 Hint

HasNext() returns true if there are nodes left to visit.

Initially HasNext() is true. After each Next(), HasNext() remains true until all nodes are visited. After the last Next(), HasNext() returns false.

🧠 Conceptual

expert

BST Iterator Modification for Reverse Order

How would you modify a BST Iterator to return nodes in descending order instead of ascending order?

A Change the stack push to traverse right children first instead of left children

B Use a queue instead of a stack to store nodes in level order

C Modify the tree to swap left and right children before iteration

D Reverse the output list after collecting all nodes in ascending order

💡 Hint

Think about how inorder traversal order changes when visiting right subtree first.

To get descending order, traverse the right subtree first by pushing right children onto the stack before left children.

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