Tree bug hunt

Questions 1 to 5 of 8

1. 1. This function should count the nodes in a tree. Called on the tiny tree (a root 1 with one left child 2), it raises AttributeError. Which change fixes it? ``python def count_nodes(node): if node.left is None and node.right is None: return 1 return 1 + count_nodes(node.left) + count_nodes(node.right) ``

   Change return 1 in the leaf check to return 0Change 1 + in the return line to 0 +Add if node is None: return 0 as the first lineSwap the two recursive calls in the return line
2. 2. This function should return the height of a tree in edges. The sample tree has root 1, children 2 and 3, and grandchildren 4, 5 and 6, so its height is 2. Calling the function on the sample tree returns 0. What is the cause? ``python def height(node): if node is None: return 0 return max(height(node.left), height(node.right)) ``

   It uses max, which returns the smallest child heightIt never adds 1 for the edge to each child, so every node returns its children's heightIt returns the number of leaves, which is 3 for the sample treeThe None check returns 1, one more than it should
3. 3. This function should return True when the value is anywhere in the tree. Called with 6 on the sample tree, it returns False, even though 6 is under node 3. ``python def contains(node, target): if node is None: return False if node.value == target: return True return contains(node.left, target) and contains(node.right, target) `` Which change makes it correct for every value?

   Change node.value == target to node.value >= targetChange return False in the None check to return TrueCheck node.right before node.left in the last lineChange and in the last line to or
4. 4. This function should swap the left and right children of every node. Calling it on the sample tree raises RecursionError. Why? ``python def mirror(node): if node is None: return temp = node.left node.left = node.right node.right = temp mirror(node) ``

   Each call passes the same node again, so the None base case is never reachedThe temp variable keeps the old left child between callsThe swap runs after the recursive calls finish, so the stack fills upThe None check returns too early for a node with one child
5. 5. This code counts the leaves with a shared counter. The variable s is the sample tree. What does it print? ``python leaf_count = 0 def count_leaves(node): global leaf_count if node is None: return 0 if node.left is None and node.right is None: leaf_count += 1 count_leaves(node.left) count_leaves(node.right) return leaf_count print('first call = ' + str(count_leaves(s))) print('second call = ' + str(count_leaves(s))) ``

   first call = 3, second call = 3first call = 0, second call = 3first call = 1, second call = 2first call = 3, second call = 6