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.