Columns and zigzags

Questions 1 to 5 of 8

1. 1. This program builds a tree and prints its top view, which is the first value seen in each column. ``cpp #include <cstddef> #include <iostream> #include <map> #include <memory> #include <queue> #include <utility> #include <vector> struct Node { int value; std::unique_ptr<Node> left; std::unique_ptr<Node> right; }; std::unique_ptr<Node> make(int value, std::unique_ptr<Node> left = nullptr, std::unique_ptr<Node> right = nullptr) { auto node = std::make_unique<Node>(); node->value = value; node->left = std::move(left); node->right = std::move(right); return node; } std::vector<int> top_view(const Node* root) { std::map<int, int> top; // column -> value of the highest node in it std::queue<std::pair<const Node*, int>> pending; pending.push({root, 0}); while (!pending.empty()) { auto [node, column] = pending.front(); pending.pop(); top.try_emplace(column, node->value); // keeps the first node seen in each column if (node->left) pending.push({node->left.get(), column - 1}); if (node->right) pending.push({node->right.get(), column + 1}); } std::vector<int> out; for (const auto& entry : top) out.push_back(entry.second); return out; } int main() { auto root = make(10, make(5, make(3), make(7, make(6))), make(20, nullptr, make(30))); const auto view = top_view(root.get()); for (std::size_t i = 0; i < view.size(); ++i) { std::cout << (i ? ", " : "") << view[i]; } std::cout << '\n'; } `` What does it print?

   3, 5, 7, 20, 303, 6, 7, 20, 303, 5, 10, 20, 3010, 5, 3, 20, 30
2. 2. In vertical_order, two nodes land in column 0 at the same depth. One is in the root's left subtree and one is in the root's right subtree. Which one is listed first in column 0?

   The node in the right subtree, because the queue adds it lastThe node in the left subtree, because the queue adds left children before right children at each depthWhichever node has the larger valueThe node that was pushed onto a stack most recently
3. 3. This program prints the zigzag levels of a tree. ``cpp #include <algorithm> #include <cstddef> #include <iostream> #include <memory> #include <queue> #include <utility> #include <vector> struct Node { int value; std::unique_ptr<Node> left; std::unique_ptr<Node> right; }; std::unique_ptr<Node> make(int value, std::unique_ptr<Node> left = nullptr, std::unique_ptr<Node> right = nullptr) { auto node = std::make_unique<Node>(); node->value = value; node->left = std::move(left); node->right = std::move(right); return node; } std::vector<std::vector<int>> zigzag(const Node* root) { std::vector<std::vector<int>> levels; if (!root) return levels; std::queue<const Node*> q; q.push(root); bool left_to_right = true; while (!q.empty()) { std::size_t count = q.size(); std::vector<int> level; for (std::size_t k = 0; k < count; ++k) { const Node* cur = q.front(); q.pop(); level.push_back(cur->value); if (cur->left) q.push(cur->left.get()); if (cur->right) q.push(cur->right.get()); } if (!left_to_right) std::reverse(level.begin(), level.end()); levels.push_back(level); left_to_right = !left_to_right; } return levels; } void print_levels(const std::vector<std::vector<int>>& levels) { for (const auto& level : levels) { std::cout << '['; for (std::size_t i = 0; i < level.size(); ++i) { std::cout << (i ? ", " : "") << level[i]; } std::cout << "]\n"; } } int main() { auto root = make(8, make(3, make(1), make(6, make(4))), make(10, nullptr, make(14))); print_levels(zigzag(root.get())); } `` What does it print?

   [8] [10, 3] [1, 6, 14] [4][8] [3, 10] [1, 6, 14] [4][8] [10, 3] [14, 6, 1] [4][8] [10, 3] [1, 6, 14]
4. 4. Put the steps of the vertical_order walk in the order the code runs them.

   Use the arrows to put the steps in order.

   1. 1.Take the front item off the queue and append its value to its column's list↑↓
   2. 2.If it has a right child, push that child with column plus 1↑↓
   3. 3.If it has a left child, push that child with column minus 1↑↓
   4. 4.Put the root and its column (0) into the queue↑↓
   5. 5.Repeat until the queue is empty↑↓
5. 5. The vertical-order walk visits the tree one whole level at a time, from top to bottom, before it goes down to the next level. What is this walk called?

   Type your answer.