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.