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.