Range sums and BST LCA

Questions 1 to 5 of 8

1. 1. What does this print? It uses the 14-node tree from the range sum lesson, built by inserting 50, 30, 70, 20, 40, 60, 80, 10, 25, 35, 45, 65, 75 and 85 in that order. It uses range_sum_pruned, reset and visits from that lesson. ``python reset() total = range_sum_pruned(root, 25, 65) print('sum=' + str(total) + ' visits=' + str(visits)) ``

   sum=300 visits=10sum=350 visits=14sum=350 visits=12sum=350 visits=10
2. 2. What does this print? It uses the same tree and function as the previous question. The call reset() runs first, so seen starts empty. ``python reset() s = range_sum_pruned(root, 36, 39) print(s, seen) ``

   0 [50, 30, 40, 45]0 [50, 30, 40, 35, 45]0 [50, 30, 40, 35]4 [50, 30, 40, 35]
3. 3. Why does the pruned range sum skip the left subtree of a node whose value is below the low bound?

   The walk has already added every value on that side, so there is nothing new to addThat left subtree is always empty when a node is below the low boundVisiting the left side would add the node's value a second timeEvery value in that left subtree is smaller than the node, so each one is also below the low bound
4. 4. The lesson's lca_bst walk runs on the 9-node tree built from 6, 2, 8, 0, 4, 3, 5, 7 and 9. For the pair 3 and 5, what does lca_bst return, and how many nodes does it visit? Set visits to 0 before the call.

   6, after 1 visit4, after 3 visits2, after 2 visits4, after 9 visits
5. 5. The function below should add the values inside [lo, hi]. On the 14-node tree from the range sum lesson, for the range [25, 65] it returns 200 instead of 350. ``python def buggy_sum(node, lo, hi): if node is None: return 0 if node.val < lo: return buggy_sum(node.left, lo, hi) if node.val > hi: return buggy_sum(node.right, lo, hi) return node.val + buggy_sum(node.left, lo, hi) + buggy_sum(node.right, lo, hi) `` Which change fixes it?

   Change the node.val > hi line so that it also adds node.valSwap the two skip lines: a node below lo goes right, and a node above hi goes leftWrap the return value in float(...), so the total is exactDelete the if node is None line