Path sums

Questions 1 to 5 of 7

1. 1. In hasRootToLeafSum, when does the function return true?

   When it reaches an inner node where remaining is 0When the path has at least two nodes and remaining is 0When it reaches a leaf where remaining is 0 or lessWhen it reaches a leaf and remaining is exactly 0
2. 2. In the example tree with target 8, the node 1 (the leaf under 2) has prefix sum 18. What does the running-sum walk look up for it, and what does it find?

   Look up 10, and find 1 for the path 5, 2, 1Look up 26, and find 0Look up 8, and find 1 for the path 10, 5, 2, 1Look up 10, and find 0, because the root is not an ancestor
3. 3. What does this program print? ``cpp #include <iostream> #include <memory> struct Node { int val = 0; std::unique_ptr<Node> left, right; }; std::unique_ptr<Node> mk(int v, std::unique_ptr<Node> l = nullptr, std::unique_ptr<Node> r = nullptr) { auto n = std::make_unique<Node>(); n->val = v; n->left = std::move(l); n->right = std::move(r); return n; } bool has(const Node* n, int remaining) { if (!n) return false; remaining -= n->val; if (!n->left && !n->right) return remaining == 0; return has(n->left.get(), remaining) || has(n->right.get(), remaining); } int main() { auto t = mk(4, mk(2, mk(-1)), mk(3)); std::cout << std::boolalpha << has(t.get(), 5) << ' ' << has(t.get(), 6) << '\n'; } ``

   false truetrue falsetrue truefalse false
4. 4. What does this program print? ``cpp #include <iostream> #include <memory> #include <vector> struct Node { int val = 0; std::unique_ptr<Node> left, right; }; std::unique_ptr<Node> mk(int v, std::unique_ptr<Node> l = nullptr, std::unique_ptr<Node> r = nullptr) { auto n = std::make_unique<Node>(); n->val = v; n->left = std::move(l); n->right = std::move(r); return n; } void collect(const Node* n, int target, int sum, std::vector<int>& path, std::vector<std::vector<int>>& out) { if (!n) return; path.push_back(n->val); sum += n->val; if (!n->left && !n->right && sum == target) out.push_back(path); collect(n->left.get(), target, sum, path, out); collect(n->right.get(), target, sum, path, out); path.pop_back(); } int main() { auto t = mk(10, mk(5, mk(3, mk(3), mk(-2)), mk(2, nullptr, mk(1))), mk(-3, nullptr, mk(11))); std::vector<int> path; std::vector<std::vector<int>> out; collect(t.get(), 18, 0, path, out); std::cout << out.size() << ' ' << path.size() << '\n'; } ``

   1 03 02 02 2
5. 5. The running-sum walk in part 3 is started once from the root of the 9-node example tree. Each real node gets exactly one lookup in prefixCount. How many lookups does one full walk make?

   Type a number.