BST Iterator Design in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare the stack used in the BST Iterator class.

DSA C++

std::stack<TreeNode*> [1];

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

Anodes

Bstack

Celements

Ddata

Attempts:

3 left

💡 Hint

Common Mistakes

Using a generic name like 'data' which is less descriptive.

Using 'stack' as variable name which can be confusing with the type.

The stack is commonly named 'nodes' to hold TreeNode pointers during iteration.

2fill in blank

medium

Complete the code to push all left children of a node onto the stack.

DSA C++

void pushLeft(TreeNode* node) {
    while (node != nullptr) {
        [1].push(node);
        node = node->left;
    }
}

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

Anodes

Bstack

Celements

Ddata

Attempts:

3 left

💡 Hint

Common Mistakes

Using the type name 'stack' instead of the variable name.

Using an undefined variable name.

The stack named 'nodes' is used to push nodes while traversing left children.

3fill in blank

hard

Fix the error in the next() method to correctly return the next smallest value.

DSA C++

int next() {
    TreeNode* node = [1].top();
    [1].pop();
    pushLeft(node->right);
    return node->val;
}

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

Aelements

Bnodes

Cstack

Ddata

Attempts:

3 left

💡 Hint

Common Mistakes

Using the type name 'stack' instead of the variable name.

Forgetting to pop the node after accessing top.

The stack variable 'nodes' holds the nodes to visit; use it to get the top node.

4fill in blank

hard

Fill both blanks to complete the hasNext() method that checks if more nodes exist.

DSA C++

bool hasNext() {
    return ![1].[2]();
}

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

Anodes

Bempty

Csize

Dtop

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'size()' instead of 'empty()' which returns a number, not boolean.

Using 'top()' which returns the top element, not a boolean.

We check if the stack 'nodes' is not empty to know if more nodes exist.

5fill in blank

hard

Fill all three blanks to complete the BST Iterator constructor initializing the stack.

DSA C++

BSTIterator(TreeNode* root) {
    [1] = std::stack<TreeNode*>();
    [2](root);
    }

private:
void [3](TreeNode* node);

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

Anodes

BpushLeft

Dstack

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'stack' as variable name which conflicts with type.

Using different names for the pushLeft method.

The constructor initializes the stack 'nodes' and calls 'pushLeft' to push left nodes. The private method is named 'pushLeft'.