BST Iterator Design in DSA Go - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main purpose of a BST Iterator?

A BST Iterator allows you to traverse a Binary Search Tree (BST) in sorted order (in-order traversal) one element at a time, without storing all elements at once.

intermediate

How does a BST Iterator typically achieve in-order traversal without recursion?

It uses a stack to keep track of nodes. It pushes left children onto the stack until it reaches the leftmost node, then processes nodes by popping from the stack and moving to right children.

beginner

In the BST Iterator design, what does the Next() method do?

Next() returns the next smallest element in the BST and advances the iterator to the following element by updating the stack accordingly.

intermediate

Why is a stack used in BST Iterator instead of a queue or list?

A stack supports last-in-first-out (LIFO) order, which matches the need to backtrack up the tree after reaching the leftmost node, enabling correct in-order traversal.

intermediate

What is the time complexity of the Next() operation in a BST Iterator?

Amortized time complexity of Next() is O(1) because each node is pushed and popped from the stack only once during the entire traversal.

What data structure does a BST Iterator commonly use to track nodes during traversal?

A Stack

B Queue

C Array

D Linked List

A stack is used to simulate the recursive in-order traversal by storing nodes to visit later.

What traversal order does a BST Iterator follow?

A Pre-order

B Post-order

C In-order

D Level-order

BST Iterator returns elements in sorted order using in-order traversal.

What does the HasNext() method in a BST Iterator indicate?

A If the BST is empty

B If there are more elements to traverse

C If the stack is empty

D If the current node has a right child

HasNext() returns true if there are still nodes left to visit in the BST.

What happens when Next() is called on a BST Iterator?

A Returns the next smallest element and updates the stack

B Returns the largest element

C Returns the root node

D Returns all remaining elements

Next() returns the next smallest element and prepares the iterator for the following call.

What is the space complexity of a BST Iterator using a stack?

A O(1)

B O(n)

C O(log n)

D O(h), where h is the height of the tree

The stack stores nodes along the path from root to the current node, which is at most the height of the tree.

Explain how a BST Iterator uses a stack to perform in-order traversal without recursion.

Think about how you would simulate recursion with a stack.

Describe the roles of the Next() and HasNext() methods in a BST Iterator.

Consider how the iterator moves forward and checks for completion.

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