Range sums and BST LCA

Questions 1 to 5 of 8

1. 1. The tree is built by inserting 8, 3, 10, 1, 6, 14, 4, 7 and 13 in that order. Using range_sum_into from this lesson, what does this print? ``cpp Stats s; range_sum_into(root.get(), 4, 10, s); std::cout << "sum=" << s.sum << " visited=" << s.visited << '\n'; ``

   sum=35 visited=9sum=35 visited=8sum=30 visited=8sum=35 visited=7
2. 2. Same nine-node tree. What does this print? ``cpp Stats s; range_sum_into(root.get(), 0, 3, s); std::cout << "sum=" << s.sum << " visited=" << s.visited << '\n'; ``

   sum=4 visited=4sum=3 visited=5sum=4 visited=5sum=0 visited=3
3. 3. On the nine-node tree, what is the lowest common ancestor of 6 and 7?

   4638
4. 4. In range_sum_into, what does the function do when a node's value is below lo?

   Visit both childrenGo left onlyStop and add nothingGo right only
5. 5. The function below should sum the values in the range lo to hi. What is the bug? ``cpp void range_sum_into(const Node* node, int lo, int hi, Stats& s) { if (node == nullptr) return; ++s.visited; s.sum += node->value; if (node->value < lo) { range_sum_into(node->right.get(), lo, hi, s); return; } if (node->value > hi) { range_sum_into(node->left.get(), lo, hi, s); return; } range_sum_into(node->left.get(), lo, hi, s); range_sum_into(node->right.get(), lo, hi, s); } ``

   It never adds a value that equals lo, so the sum is too smallIt visits the children in the wrong order, which changes the sumIt adds every visited node before the range check, so values outside the range such as 3 and 14 are countedIt stops at the first node in range, so it misses the rest of the range