BST iterator

Questions 1 to 5 of 6

1. 1. Using Tree, insert and BstIterator from this lesson, what does this code print? ``cpp Tree a; for (int k : {5, 2, 8, 1, 3}) a = insert(std::move(a), k); BstIterator it(a.get()); std::cout << it.stack_size() << ' '; std::cout << it.next() << ' ' << it.stack_size() << '\n'; ``

   3 1 33 1 21 1 02 1 2
2. 2. Using the same tree as the question before (keys 5, 2, 8, 1 and 3 inserted in that order) and DescendingIterator from this lesson, what does this code print? ``cpp DescendingIterator di(a.get()); while (di.has_next()) std::cout << di.next() << ' '; ``

   1 2 3 5 88 5 2 1 35 8 3 2 18 5 3 2 1
3. 3. In BstIterator::next(), why does the code call push_left on node->right, and not just push node->right on the stack?

   Because the keys in the right subtree are smaller than node, so they must be read firstBecause the smallest key of the right subtree sits at the bottom of its left branch, and it must come nextBecause push_left removes the right child from the treeBecause a std::stack cannot hold a null pointer
4. 4. A tree of the keys 1 to 1000 is built by inserting them in ascending order, and BstIterator walks the whole tree. What is the peak stack size?

   125001000
5. 5. What is the total work of a full walk over n keys with BstIterator, counting every push and pop?

   O(1)O(log n)O(n)O(n^2)