Mirror, symmetry and subtrees

Questions 1 to 5 of 8

1. 1. What does this program print? (Node has an int val and std::unique_ptr<Node> left, right, and invert swaps the two children of every node.) ``cpp #include <iostream> #include <memory> #include <utility> struct Node { int val = 0; std::unique_ptr<Node> left, right; }; std::unique_ptr<Node> mk(int v, std::unique_ptr<Node> l = nullptr, std::unique_ptr<Node> r = nullptr) { auto n = std::make_unique<Node>(); n->val = v; n->left = std::move(l); n->right = std::move(r); return n; } void invert(Node* n) { if (n == nullptr) return; std::swap(n->left, n->right); invert(n->left.get()); invert(n->right.get()); } void dump(const Node* n) { if (n == nullptr) { std::cout << ". "; return; } std::cout << n->val << ' '; dump(n->left.get()); dump(n->right.get()); } int main() { auto t = mk(4, mk(2, mk(1)), mk(7)); invert(t.get()); dump(t.get()); std::cout << '\n'; } ``

   4 2 1 . . . 7 . .4 7 . 2 . 1 . . .4 7 . . 2 . 1 . .7 4 . . 2 . 1 . .
2. 2. What does this program print? (same_tree and is_subtree are the lesson's functions, and mk builds a node from a value and two optional children.) ``cpp #include <iostream> #include <memory> #include <utility> struct Node { int value = 0; std::unique_ptr<Node> left, right; }; std::unique_ptr<Node> mk(int v, std::unique_ptr<Node> l = nullptr, std::unique_ptr<Node> r = nullptr) { auto n = std::make_unique<Node>(); n->value = v; n->left = std::move(l); n->right = std::move(r); return n; } bool same_tree(const Node* a, const Node* b) { if (a == nullptr || b == nullptr) { return a == b; } return a->value == b->value && same_tree(a->left.get(), b->left.get()) && same_tree(a->right.get(), b->right.get()); } bool is_subtree(const Node* root, const Node* sub) { if (sub == nullptr) { return true; } if (root == nullptr) { return false; } return same_tree(root, sub) || is_subtree(root->left.get(), sub) || is_subtree(root->right.get(), sub); } int main() { std::cout << std::boolalpha; auto big = mk(10, mk(4, mk(1), mk(6)), mk(7, nullptr, mk(9, mk(8)))); auto s1 = mk(6); auto s2 = mk(7, mk(9)); std::cout << is_subtree(big.get(), s1.get()) << ' ' << is_subtree(big.get(), s2.get()) << '\n'; } ``

   false truetrue falsetrue truefalse false
3. 3. The Node struct has an int val and unique_ptr children left and right. isSymmetric should return false for a root 1 that has only a left child 2, but this version returns true. What is the bug? ``cpp bool areMirrors(const Node* a, const Node* b) { if (a == nullptr || b == nullptr) return true; return a->val == b->val && areMirrors(a->left.get(), b->right.get()) && areMirrors(a->right.get(), b->left.get()); } bool isSymmetric(const Node* root) { if (root == nullptr) return true; return areMirrors(root->left.get(), root->right.get()); } ``

   It crosses the sides correctly, but it never compares the valuesIt calls invert, which changes the tree it is comparingIt never recurses into grandchildren, so deep differences are missedWhen only one side is empty it returns true, so a root with only a left child passes as symmetric
4. 4. is_subtree should return true when the node 9 with a left child 8 appears inside the big tree whose root is 10. This version returns false. What is the bug? ``cpp bool is_subtree(const Node* root, const Node* sub) { if (sub == nullptr) return true; return same_tree(root, sub); } ``

   It returns false whenever sub is nullptr, so an empty sub is never foundIt calls same_tree with a null pointer, which always crashesIt compares only the root of big with sub, so it never tries the nodes below the rootIt compares the left child of big with the right child of sub
5. 5. Why does the lesson include a queue-based version of the symmetry check?

   It is faster, because it visits each node twiceIt works only on trees with no negative valuesThe recursion depth grows with the tree height, so a very deep tree can run out of call stack, while the queue stores its pairs on the heapIt skips the null check, because the queue holds only real nodes