Path sums

Questions 1 to 5 of 7

1. 1. The collect_paths function stores list(path) in the result instead of path. Why?

   A copy runs faster than the original list.The shared list keeps changing as the walk backtracks, so only a copy keeps the path as it was at the leaf.Python does not allow one list to hold another list.The copy removes the duplicate values that come from the root.
2. 2. In has_path_sum, which test marks a node as a leaf?

   node.left is None onlyremaining == node.valuenode.left is None and node.right is Nonenode is None
3. 3. What does this program print? ``python class TreeNode: def __init__(self, value, left=None, right=None): self.value = value self.left = left self.right = right def has_path_sum(node, remaining): if node is None: return False left = remaining - node.value if node.left is None and node.right is None: return left == 0 return has_path_sum(node.left, left) or has_path_sum(node.right, left) root = TreeNode(1) root.left = TreeNode(2) root.right = TreeNode(3) root.right.left = TreeNode(4) print(has_path_sum(root, 3), has_path_sum(root, 4), has_path_sum(root, 8)) ``

   True False TrueTrue True TrueFalse False TrueTrue False False
4. 4. What does this program print? ``python class TreeNode: def __init__(self, value, left=None, right=None): self.value = value self.left = left self.right = right def count_any_path(root, target): prefix_count = {0: 1} return count_from(root, 0, target, prefix_count) def count_from(node, running_sum, target, prefix_count): if node is None: return 0 running_sum += node.value count = prefix_count.get(running_sum - target, 0) prefix_count[running_sum] = prefix_count.get(running_sum, 0) + 1 count += count_from(node.left, running_sum, target, prefix_count) count += count_from(node.right, running_sum, target, prefix_count) prefix_count[running_sum] -= 1 return count root = TreeNode(3) root.right = TreeNode(-3) root.right.right = TreeNode(3) print(count_any_path(root, 3), count_any_path(root, 0)) ``

   2 33 32 23 2
5. 5. Which statements about the running-sum method for any-path sums are true? Pick all that apply.

   Pick every answer that is true.

   The map starts with the entry 0 with count 1, so a path that starts at the root is counted.The entry for a node's running sum is removed after both of its children are visited.One walk of the tree counts every downward path, without trying each node as a start.Removing the map entry before the children are visited makes the count go up for paths that start above the node.The method works only when every value in the tree is positive.