Iterative traversals

Questions 1 to 5 of 8

1. 1. What does this print? ``cpp auto a = make(5, make(3, make(1), make(4)), make(8)); for (int x : inorder(a.get())) std::cout << x << ' '; ` inorder is the stack version from this lesson, and make` builds a node.

   1 3 4 5 85 3 1 4 81 4 3 8 58 5 4 3 1
2. 2. What does this print? ``cpp auto p = make(8, make(4, make(2), make(6)), make(12)); std::size_t peak = 0; preorder_with_peak(p.get(), peak); std::cout << "peak stack size: " << peak << '\n'; ` preorder_with_peak` is the version from this lesson that records the largest stack size.

   1235
3. 3. What does this print? ``cpp auto t = make(10, make(6, make(2), make(7)), make(14, make(12), nullptr)); for (int x : postorder(t.get())) std::cout << x << ' '; ` postorder is the one-stack version with the last` pointer from the previous lesson.

   10 6 2 7 14 122 7 6 12 14 102 6 7 12 14 102 7 6 14 12 10
4. 4. Why does the postorder version need a last pointer, while the preorder version does not?

   Postorder needs last to remember the parent of each node, and the stack has no parent linkPreorder pushes both children at once, so it never has to decide whether a child is finishedlast caches the value of the left subtree so that postorder can add it to the right subtreePostorder sees a node twice, once on the way down and once after its right subtree, and last tells the node on top whether it is coming back from its right child
5. 5. The kth_smallest function from this lesson is called on the 7-node tree with root 4 and k = 4. What does it return, and what happens to the rest of the tree?

   3, because k counts from zero, so the fourth value is the one at index 36, because the walk goes right before it goes left4, because the walk stops as soon as the fourth value is visited, so 5, 6 and 7 are never visited4, but only after the whole tree has been visited