BST Iterator Design in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the stack in the BST iterator constructor.

DSA Go

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

Drag options to blanks, or click blank then click option'

ApushLeft(root, &stack)

BpushLeft(root, stack)

CpushRight(root, &stack)

DpushRight(root, stack)

Attempts:

3 left

💡 Hint

Common Mistakes

Passing stack by value instead of pointer

Calling pushRight instead of pushLeft

The constructor must call pushLeft with the root and the pointer to the stack to initialize it correctly.

2fill in blank

medium

Complete the code to implement the Next() method that returns the next smallest element.

DSA Go

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

Drag options to blanks, or click blank then click option'

ApushLeft(node.Right, &this.stack)

BpushLeft(node.Left, &this.stack)

CpushRight(node.Right, &this.stack)

DpushRight(node.Left, &this.stack)

Attempts:

3 left

💡 Hint

Common Mistakes

Calling pushLeft on node.Left instead of node.Right

Using pushRight instead of pushLeft

After popping the top node, we push all left children of its right child to the stack.

3fill in blank

hard

Fix the error in the HasNext() method to correctly check if there are more elements.

DSA Go

func (this *BSTIterator) HasNext() bool {
    return [1]
}

Drag options to blanks, or click blank then click option'

Alen(this.stack) == 0

Blen(this.stack) > 0

Cthis.stack != nil

Dthis.stack == nil

Attempts:

3 left

💡 Hint

Common Mistakes

Checking if stack is nil instead of length

Returning true when stack is empty

HasNext returns true if the stack has any nodes left, so check if length > 0.

4fill in blank

hard

Fill both blanks to complete the pushLeft helper function that pushes all left children onto the stack.

DSA Go

func pushLeft(node *TreeNode, stack *([]*TreeNode)) {
    for node != nil {
        *stack = append(*stack, [1])
        node = [2]
    }
}

Drag options to blanks, or click blank then click option'

Anode

Bnode.Val

Cnode.Left

Dnode.Right

Attempts:

3 left

💡 Hint

Common Mistakes

Appending node.Val instead of node

Moving to node.Right instead of node.Left

We append the current node itself and then move to its left child in the loop.

5fill in blank

hard

Fill all three blanks to complete the BSTIterator struct and its constructor with stack initialization.

DSA Go

type BSTIterator struct {
    [1] []*TreeNode
}

func Constructor(root *TreeNode) BSTIterator {
    stack := [2]
    [3]
    return BSTIterator{stack: stack}
}

Drag options to blanks, or click blank then click option'

Astack

B[]*TreeNode{}

CpushLeft(root, &stack)

Dstack := []*TreeNode{}

Attempts:

3 left

💡 Hint

Common Mistakes

Declaring stack as a pointer instead of slice

Not initializing stack before pushLeft

Calling pushLeft without passing pointer to stack

The struct has a stack field which is a slice of TreeNode pointers. The constructor initializes stack as empty slice and calls pushLeft to fill it.

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