Recovering and trimming

Questions 1 to 5 of 8

1. 1. The trim_recursive function from this lesson is called on this tree with the range 2 to 8. What does the program print? ``python t = TreeNode(5, TreeNode(3, leaf(1), leaf(4)), TreeNode(8, leaf(7), leaf(9))) print(inorder(trim_recursive(t, 2, 8))) ``

   [4, 5, 7, 8][3, 4, 5, 7, 8, 9][3, 4, 5, 7, 8][1, 3, 4, 5, 7, 8]
2. 2. The recover_bst function from the module's recovery lesson fixes the tree below. What does the program print? ``python u = TreeNode(5, TreeNode(8, leaf(1), leaf(4)), TreeNode(3, leaf(7), leaf(9))) recover_bst(u) print(inorder(u)) ``

   [1, 8, 4, 5, 7, 3, 9][1, 3, 4, 5, 7, 8, 9][1, 3, 4, 5, 8, 7, 9][1, 4, 3, 5, 7, 8, 9]
3. 3. The function below is meant to trim a BST to the range low to high, but it has a bug. Which statement describes it? ``python def trim_recursive(node, low, high): if node is None: return None if node.val < low: return None if node.val > high: return trim_recursive(node.left, low, high) node.left = trim_recursive(node.left, low, high) node.right = trim_recursive(node.right, low, high) return node ``

   The None check should return node instead of NoneA too-small node returns None, which throws away its right subtree, and that subtree can hold values in rangeThe too-big branch should return the right subtree instead of the leftThe in-range branch should skip trimming the left child, because the left side is already sorted
4. 4. This change is made to trim_iterative. The while in the child-fixing loop is replaced with this if: ``python if node.left is not None and node.left.val < low: node.left = node.left.right `` The tree has root 10, its left child is 2, and 2's right child is 3. The range is 4 to 20. What goes wrong?

   The left child of 10 becomes None, so the value 3 is lost along with 2The root 10 is removed, because the if checks the root firstThe left child of 10 becomes 3, which is also below 4, so the value 3 stays in the treeNothing is wrong, because an if and a while give the same result for every tree
5. 5. Put the steps of the recursive trim_recursive in the order the function checks them for one node.

   Use the arrows to put the steps in order.

   1. 1.If the node's value is less than low, return the trimmed right subtree↑↓
   2. 2.Otherwise, trim the left and right children, store the results as the new links, and return the node↑↓
   3. 3.If the node's value is greater than high, return the trimmed left subtree↑↓
   4. 4.If the node is None, return None↑↓