Recovering and trimming

Questions 1 to 5 of 8

1. 1. The Node, insert, inorder, destroy and recursive trim functions are the ones from this lesson. What does this main print? ``cpp int main() { Node* root = nullptr; for (int v : {10, 4, 15, 2, 6, 12, 20}) root = insert(root, v); root = trim(root, 5, 13); vector<int> out; inorder(root, out); for (int v : out) cout << v << ' '; cout << '\n'; destroy(root); } ``

   2 4 6 10 126 10 126 10 12 1510 6 12
2. 2. Using Node, insert, findNode and inorder from this lesson's recovery program, what does this code print? ``cpp Node* tree = nullptr; for (int v : {5, 3, 8, 1, 4, 7, 9, 2, 6}) tree = insert(tree, v); swap(findNode(tree, 3)->val, findNode(tree, 7)->val); vector<int> out; inorder(tree, out); for (int v : out) cout << v << ' '; ``

   1 2 3 4 5 6 7 8 91 7 3 4 5 6 2 8 91 2 7 4 5 3 6 8 91 2 7 4 5 6 3 8 9
3. 3. The removal branches of this recursive trim are correct. What is wrong with the code? ``cpp Node* trim(Node* node, int low, int high) { if (!node) return nullptr; if (node->val < low) { Node* keep = trim(node->right, low, high); destroy(node->left); delete node; return keep; } if (node->val > high) { Node* keep = trim(node->left, low, high); destroy(node->right); delete node; return keep; } trim(node->left, low, high); node->right = trim(node->right, low, high); return node; } ``

   Nothing, the call on node->left is correct as writtenThe range check uses < and > where it should use <= and >=, so boundary values are removednode->left is not updated, so if the left child is removed, node->left still points at freed memoryThe function returns before it trims the right side
4. 4. The walk function finds the two nodes that hold the wrong values, and Fix keeps them as first and second. What does recoverBST do when it runs this code? ``cpp void recoverBST(Node* root) { Fix f; walk(root, f); swap(f.first, f.second); } ``

   It swaps the two pointers stored in f, so no node value changes and the tree stays brokenIt swaps the two child pointers of the rootIt swaps the two node values, so the tree is fixedIt crashes at once, because swap cannot take pointers
5. 5. Put the steps that the recursive trim takes for a node whose value is less than low in the correct order.

   Use the arrows to put the steps in order.

   1. 1.Destroy the left subtree↑↓
   2. 2.Return the kept subtree to the caller↑↓
   3. 3.Delete the node itself↑↓
   4. 4.Call trim on the right child and keep the result↑↓