Tree bug hunt

Questions 1 to 5 of 8

1. 1. The Node struct is the one from the lesson (value, left, right). What does this program print? ``cpp int heightBugBase(const Node* n) { if (n == nullptr) return 1; return 1 + std::max(heightBugBase(n->left.get()), heightBugBase(n->right.get())); } int main() { Node a(1); std::cout << heightBugBase(&a) << std::endl; a.right = std::make_unique<Node>(3); std::cout << heightBugBase(&a) << std::endl; } ``

   Prints 1, then 2Prints 2, then 2Prints 2, then 3Prints 1, then 3
2. 2. This function should return the height of a tree in edges, but it is wrong for some trees. Which tree gives a wrong answer? ``cpp int heightBugLeft(const Node* n) { if (n == nullptr) return -1; return 1 + heightBugLeft(n->left.get()); } ``

   A root with only a right child, because the function never calls itself on n->right, so it returns 0 instead of 1A tree with one node, because the base case returns -1 instead of 0A chain of three nodes that goes down the left side, because the base case should return 0A tree with more than eight nodes, because the recursion has no end
3. 3. The sum of the test tree should be 36, but this function returns 13 for it. What is the bug? ``cpp int sumBugRight(const Node* n) { if (n == nullptr) return 0; return n->value + sumBugRight(n->left.get()); } ``

   The base case returns 0 for nullptr, which should be -1 so that empty subtrees are not addedThe parameter is const Node*, so the function cannot read n->valueEach node adds its value twice, so the total is counted too highThe return statement never calls the function on n->right, so the right subtree is left out of the sum
4. 4. The program calls countLeavesBug(root.get()) twice on the test tree and prints leafCount after each call. The first line says 2 and the second says 4. Why? ``cpp int leafCount = 0; void countLeavesBug(const Node* n) { if (n == nullptr) return; if (n->left == nullptr && n->right == nullptr) ++leafCount; countLeavesBug(n->left.get()); countLeavesBug(n->right.get()); } ``

   The base case returns 0 on the second call, so no leaves are addedleafCount is a global that is never reset, so the second call adds 2 more to the 2 from the first callThe right child is visited twice on each call, so every leaf is counted twicestd::cout prints the counter before the second call has finished
5. 5. Calling countNodesBug on the test tree makes the program exit with code 139 and print nothing. What is the cause? ``cpp int countNodesBug(const Node* n) { return 1 + countNodesBug(n->left.get()) + countNodesBug(n->right.get()); } ``

   It returns int, but Node holds unique_ptr children, which cannot be countedIt adds 1 for every node, so the total is larger than the real countIt has no base case for nullptr, so it reads n->left on a null pointer and the program crashesThe parameter is missing const, which lets the function change the tree