BST Iterator Design in DSA Typescript - 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 achieve O(h) space complexity, where h is the tree height?

It uses a stack to store nodes along the path from the root to the current node, pushing only left children. This stack size is at most the height of the tree, so space is O(h).

beginner

In BST Iterator design, what does the next() method do?

The next() method returns the next smallest element in the BST by popping the top node from the stack and then pushing all left children of its right subtree.

intermediate

Why do we push left children onto the stack during BST Iterator initialization and after calling next()?

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

advanced

What is the time complexity of the next() method in a BST Iterator over n calls?

Amortized time complexity is O(1) per call because each node is pushed and popped exactly once during the entire iteration.

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

A Linked List

B Queue

C Array

D Stack

A stack is used to keep track of nodes along the path to the next smallest element.

What traversal order does a BST Iterator follow?

A In-order

B Pre-order

C Post-order

D Level-order

BST Iterator returns elements in sorted order using in-order traversal.

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

A If the stack is empty

B If the current node has a right child

C If the stack is not empty

D If the tree root is null

hasNext() returns true if there are still nodes to visit, which means the stack is not empty.

When next() is called, after popping a node, what nodes are pushed onto the stack?

A All right children of the popped node

B All left children of the popped node's right subtree

C All left children of the popped node's left subtree

D All children of the popped node

After popping, we push all left children of the right subtree to maintain in-order traversal.

What is the worst-case space complexity of a BST Iterator for a balanced BST?

A O(log n)

B O(n)

C O(1)

D O(n log n)

For a balanced BST, the height h is O(log n), so space complexity is O(h) = O(log n).

Explain how a BST Iterator uses a stack to return elements in sorted order.

Think about in-order traversal and how the stack helps track nodes.

Describe the time and space complexity of the BST Iterator and why it is efficient.

Consider how often nodes are pushed/popped and the maximum stack size.