Embercode: AI-powered software engineer course

1. The BstIterator class from this lesson is built on this tree. What does the program print? ``

python
it = BstIterator(build(10, 5, 15, 3, 7))
next(it)
print(next(it), it.peek())

``

5 73 55 107 10

2. What does this program print? ``

python
it = BstIterator(build(8, 4, 12, 2, 6))
n = 0
for v in it:
    if v > 4:
        n += 1
print(n, next(it, None) is None)

``

5 True3 True4 False3 False

3. Why is the iterator's stack never bigger than the height of the tree?

Each node on the stack lies on one path down from the root, and a path has at most one node per levelA right child is always one level below its parent, so the stack grows by one per levelOnly leaves go on the stack, and a tree has about as many leaves as levelsThe stack holds a copy of every value in the tree, so it is at most the number of levels

4. After __next__ pops a node X, what does the iterator push next?

Nothing, because the left path was already pushed when X was first reachedX.right alone, if X.right is not NoneThe left path of X.left, which is the next smaller valueThe left path of X.right, using self._push_left_path(X.right), which pushes nothing if X has no right child

5. Insert the values 9, 8, 7, 6, 5, 4, 3, 2, 1 into a BST, one at a time in that order. Then run a full walk with BstIterator and read its max_size afterwards. What is it?

Type a number.

BST iterator