BST Iterator Design in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main purpose of a BST Iterator?

A BST Iterator allows us 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 store its state internally?

It uses a stack to keep track of nodes. The stack stores the path from the root to the current node, allowing the iterator to move to the next smallest element efficiently.

intermediate

Explain the role of the 'next()' function in a BST Iterator.

The 'next()' function returns the next smallest element in the BST. It pops the top node from the stack, processes it, and then pushes all the left children of the popped node's right child onto the stack.

beginner

Why does the BST Iterator push left children onto the stack during initialization and after visiting a node?

Because in-order traversal visits left children first, pushing left children ensures the smallest elements are on top of the stack, ready to be returned by 'next()'.

intermediate

What is the time complexity of the 'next()' and 'hasNext()' operations in a BST Iterator?

'hasNext()' runs in O(1) time. 'next()' runs in average O(1) amortized time because each node is pushed and popped exactly once.

What data structure is commonly used inside a BST Iterator to track nodes?

A Stack

B Queue

C Array

D Linked List

A stack is used to keep track of nodes along the path to the current node for in-order traversal.

What does the 'next()' method of a BST Iterator return?

A The last visited node value

B The next smallest element in the BST

C The root node value

D The next largest element in the BST

'next()' returns the next smallest element following in-order traversal.

When initializing a BST Iterator, which nodes are pushed onto the stack first?

A All left children from the root down

B All leaf nodes

C All right children

D Only the root node

All left children from the root down to the leftmost node are pushed to start with the smallest element.

What is the average time complexity of the 'next()' operation in a BST Iterator?

A O(n)

B O(log n)

C O(1) amortized

D O(n log n)

'next()' runs in O(1) amortized time because each node is pushed and popped once.

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

A If there is a next larger element

B If the current node has a right child

C If the BST is empty

D If the stack is not empty, meaning more elements remain

'hasNext()' returns true if the stack is not empty, meaning there are more nodes to visit.

Describe how a BST Iterator uses a stack to perform in-order traversal step-by-step.

Think about how in-order traversal visits nodes left-root-right.

Explain why the BST Iterator's next() method has O(1) amortized time complexity.

Consider how many times each node is handled during iteration.