Debugging lab: tree recursion bugs

Why this matters

Tree functions are usually recursive. A recursive function is one that calls itself on a smaller piece of the problem. For a tree, the smaller piece is a subtree, which is one child together with everything below it. A function that counts nodes calls itself on the left child, calls itself on the right child, and adds the two answers to 1 for the current node.

Recursive code is easy to write and easy to read wrong. The code looks correct at a glance, and the bug only shows up on a tree with a particular shape. A function can pass a test on a tree that has two children and fail on a tree that has one. This lesson gives you five broken tree functions. You run them, compare their answers with the answers you expect, find the cause, and fix them.

Here every tree is a pointer tree, where each node is an object that holds a value and two std::unique_ptr children (a smart pointer that owns its node and frees it automatically). The earlier lessons of this module cover the traversals and the height in more detail, so this lesson focuses on finding bugs.

Words used in this lesson

Recursion is a function that calls itself. The base case is the input where the function stops calling itself and returns an answer directly. For a tree function, the usual base case is the empty tree, which is a null pointer. A null pointer is a pointer that points to nothing, and it is written nullptr in C++.

The return value is what a function sends back to the code that called it. A global variable is a variable declared outside every function. Every call shares it, so a change made by one call is still there for the next call. A sanitizer is a compiler option that checks the program while it runs, and it prints a report when it finds a memory error. The report includes the line of code that caused the problem.

Height is measured in edges in this lesson. An edge is the line between a parent and a child. The height of a tree is the number of edges on the longest path from the root down to a leaf. A single node has height 0.

The test tree

Every function in this lesson runs on the same tree. Its shape is below. The numbers are the values stored in the nodes.

        1
      /   \
     2     3
    /       \
   4         5
  /           \
 6             7
                \
                 8

Write down the answers you expect before you run any code. For this tree:

• The number of nodes is 8.
• The height is 4, measured in edges. The longest path is 1, 3, 5, 7, 8, which has 4 edges.
• The sum of all the values is 36.
• The number of leaves is 2. The leaves are 6 and 8.

The left path, 1, 2, 4, 6, is shorter than the right path. A function that looks at only one side will get the wrong height. The lab functions hit that case on purpose.

A method for finding recursion bugs

Use the same four steps for every bug in this lesson.

1. Write the expected answer for three inputs: the empty tree, a tree with one node, and the test tree. Do this on paper first.
2. Look at the base case. Which input makes the function stop? Is the value it returns right for that input?
3. Trace one call by hand on a tree with two nodes. Write each call and the value it returns, one line at a time.
4. Look for state that outlives a call. A global variable or a static variable keeps its value between calls. Ask what happens when the function runs a second time.

When a program crashes, add -g and -fsanitize=address,undefined to the compile command. Those flags add line numbers to the report, and they check memory errors as the program runs. The compile command looks like this:

g++ -std=c++20 -Wall -g -fsanitize=address,undefined -o lab lab.cpp && ./lab

Compile without the sanitizer for the normal run. The sanitizer slows the program down, and it is only needed when something goes wrong.

Bug 1: a missing base case

A base case stops the recursion. This function has none for the empty tree:

#include <iostream>
#include <memory>
 
struct Node {
    int value;
    std::unique_ptr<Node> left;
    std::unique_ptr<Node> right;
    explicit Node(int v) : value(v) {}
};
 
std::unique_ptr<Node> buildTree() {
    auto root = std::make_unique<Node>(1);
    root->left = std::make_unique<Node>(2);
    root->right = std::make_unique<Node>(3);
    return root;
}
 
// BUG E: there is no base case for an empty subtree.
int countNodesBug(const Node* n) {
    return 1 + countNodesBug(n->left.get()) + countNodesBug(n->right.get());
}
 
int main() {
    auto root = buildTree();
    std::cout << "count: " << countNodesBug(root.get()) << "\n";
}

Compile it with the normal flags first:

g++ -std=c++20 -Wall -g -o crash crash.cpp

The compiler warns about the recursion:

crash.cpp: In function ‘int countNodesBug(const Node*)’:
crash.cpp:19:5: warning: infinite recursion detected [-Winfinite-recursion]
   19 | int countNodesBug(const Node* n) {
      |     ^~~~~~~~~~~~~
crash.cpp:20:29: note: recursive call
   20 |     return 1 + countNodesBug(n->left.get()) + countNodesBug(n->right.get());
      |                ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~

The warning says the function may call itself forever. That is not quite what happens here. At a leaf, the function calls itself on a null pointer. The first thing that call does is read n->left, and that read crashes the program. Run the program:

./crash; echo "exit=$?"

The output is:

exit=139

The program prints nothing. The exit code 139 means the operating system stopped the program with a segmentation fault, which is a read or write to memory the program is not allowed to touch. The count: line never appears, because the program died before it printed the result.

Compile the same file with the sanitizer to see where the crash happens:

g++ -std=c++20 -Wall -g -fsanitize=address,undefined -o crash_asan crash.cpp && ./crash_asan

The report starts with lines like these. The process number and the addresses change on each run, so your numbers will differ:

crash.cpp:20:41: runtime error: member access within null pointer of type 'const struct Node'
crash.cpp:20:33: runtime error: member access within null pointer of type 'const struct Node'
AddressSanitizer:DEADLYSIGNAL
==215880==ERROR: AddressSanitizer: SEGV on unknown address 0x000000000008 (pc 0x6250edd1f1c8 bp 0x7fff372eef40 sp 0x7fff372eef20 T0)
==215880==The signal is caused by a READ memory access.
==215880==Hint: address points to the zero page.

The line member access within null pointer says the code used -> on a null pointer. The address 0x8 is the offset of the left field inside a Node that starts at address 0. So the program read a field of nothing. The report also prints the frames below the crash. The first ones point to crash.cpp:20, which is the recursive line, and the last one points to main.

The fix is a base case for the empty tree. An empty tree has no nodes, so it returns 0:

int countNodes(const Node* n) {
    if (n == nullptr) return 0;
    return 1 + countNodes(n->left.get()) + countNodes(n->right.get());
}

With this base case, the function returns 8 for the test tree. The count of a one-node tree is 1, because its two children are empty and each returns 0.

Before you move on, check one detail. The base case must come before any use of n->. Putting the check after the line that reads n->left does not help, because the read already happened.

Bug 2: the base case returns the wrong value

This function has a base case, but the value is wrong:

// BUG A: the empty tree returns 1, so every count is one too high.
int heightBugBase(const Node* n) {
    if (n == nullptr) return 1;
    return 1 + std::max(heightBugBase(n->left.get()), heightBugBase(n->right.get()));
}

Here is the test tree run through this function. Each empty child returns 1. A leaf, such as node 8, then has two empty children, so it returns 1 + max(1, 1), which is 2. The leaf should have returned 1 for one node. The extra 1 spreads up the tree, so the root's answer is one more than the number of nodes on the longest path.

The longest path has 5 nodes, 1, 3, 5, 7, 8. The function returns 6. This is the output of the lab program, which is in the next section, and it says got 6 where 4 was expected.

The fix is to return -1 for the empty tree. Then a leaf returns 1 + max(-1, -1), which is 0, and the answer counts edges:

int height(const Node* n) {
    if (n == nullptr) return -1;
    return 1 + std::max(height(n->left.get()), height(n->right.get()));
}

The fixed function returns 4 for the test tree.

Another way to get a correct answer is to return 0 for the empty tree and call the answer "nodes on the longest path". That gives 5 for the test tree. Either answer is correct, but the name has to match the number. A function called height that returns 5 for this tree is wrong for the height definition in this lesson.

Bug 3: a wrong return that looks at one side only

This function follows only the left child:

// BUG B: only the left side is looked at.
int heightBugLeft(const Node* n) {
    if (n == nullptr) return -1;
    return 1 + heightBugLeft(n->left.get());
}

The base case is right, and the recursion is right for a tree that is only a left chain. It fails when the right side is deeper. The test tree's left path is 1, 2, 4, 6, which has 3 edges. The right path has 4 edges. The function returns 3.

The bug is a missing call. The answer should be the bigger of the two sides, so the fix calls the function on both children and takes the maximum:

int heightBothSides(const Node* n) {
    if (n == nullptr) return -1;
    return 1 + std::max(heightBothSides(n->left.get()), heightBothSides(n->right.get()));
}

This pattern shows up in every tree function that asks about the longest path. If a function asks about "the deepest" or "the longest", it must look at both children.

Bug 4: a subtree left out of the sum

This function adds up the values, but it does not visit the right child:

// BUG C: the right subtree is never added.
int sumBugRight(const Node* n) {
    if (n == nullptr) return 0;
    return n->value + sumBugRight(n->left.get());
}

The function returns 13. That is the sum of the left path, 1 + 2 + 4 + 6. The expected sum of all eight values is 36. The right subtree has values 3, 5, 7, and 8, and none of them is counted.

The fix adds the sum of the right subtree:

int sum(const Node* n) {
    if (n == nullptr) return 0;
    return n->value + sum(n->left.get()) + sum(n->right.get());
}

A quick test for this bug is a root with a single right child, the values 1 and 3. The function returns 1, and the sum is 4.

Bug 5: a counter that is not reset

This function counts the leaves, and it stores the count in a global variable:

// BUG D: the counter is global and is never reset.
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());
}

Call it twice on the same tree and print the counter after each call:

countLeavesBug(root.get());
std::cout << "leaves, first call: expected 2, got " << leafCount << "\n";
countLeavesBug(root.get());
std::cout << "leaves, second call: expected 2, got " << leafCount << "\n";

The first call is right, and the second is wrong. Each call adds to leafCount, and nothing sets it back to 0. So the second call makes it 4. The function is correct when it runs once. Nothing in its code says it runs once.

The fix removes the global. The function returns the count for its own subtree, and the caller adds nothing by hand:

int countLeaves(const Node* n) {
    if (n == nullptr) return 0;
    if (n->left == nullptr && n->right == nullptr) return 1;
    return countLeaves(n->left.get()) + countLeaves(n->right.get());
}

A second fix is to set leafCount = 0; before each call. It works, but it depends on the caller remembering to do it. A function with a return value has no shared state to forget about, so the return value is the better design.

The lab, run

The file below holds the first four buggy functions. It runs each one on the test tree and prints what it expects next to what it got. Save it as lab.cpp:

#include <algorithm>
#include <iostream>
#include <memory>
 
struct Node {
    int value;
    std::unique_ptr<Node> left;
    std::unique_ptr<Node> right;
    explicit Node(int v) : value(v) {}
};
 
/* The tree used in every test:
         1
       /   \
      2     3
     /       \
    4         5
   /           \
  6             7
                 \
                  8
*/
std::unique_ptr<Node> buildTree() {
    auto root = std::make_unique<Node>(1);
    root->left = std::make_unique<Node>(2);
    root->right = std::make_unique<Node>(3);
    root->left->left = std::make_unique<Node>(4);
    root->left->left->left = std::make_unique<Node>(6);
    root->right->right = std::make_unique<Node>(5);
    root->right->right->right = std::make_unique<Node>(7);
    root->right->right->right->right = std::make_unique<Node>(8);
    return root;
}
 
// BUG A: the empty tree returns 1, so every count is one too high.
int heightBugBase(const Node* n) {
    if (n == nullptr) return 1;
    return 1 + std::max(heightBugBase(n->left.get()), heightBugBase(n->right.get()));
}
 
// BUG B: only the left side is looked at.
int heightBugLeft(const Node* n) {
    if (n == nullptr) return -1;
    return 1 + heightBugLeft(n->left.get());
}
 
// BUG C: the right subtree is never added.
int sumBugRight(const Node* n) {
    if (n == nullptr) return 0;
    return n->value + sumBugRight(n->left.get());
}
 
// BUG D: the counter is global and is never reset.
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());
}
 
int main() {
    auto root = buildTree();
 
    std::cout << "height: expected 4, got " << heightBugBase(root.get()) << "\n";
    std::cout << "height (left side only): expected 4, got " << heightBugLeft(root.get()) << "\n";
    std::cout << "sum: expected 36, got " << sumBugRight(root.get()) << "\n";
 
    countLeavesBug(root.get());
    std::cout << "leaves, first call: expected 2, got " << leafCount << "\n";
    countLeavesBug(root.get());
    std::cout << "leaves, second call: expected 2, got " << leafCount << "\n";
}

Compile and run it:

g++ -std=c++20 -Wall -o lab lab.cpp && ./lab

The output is:

height: expected 4, got 6
height (left side only): expected 4, got 3
sum: expected 36, got 13
leaves, first call: expected 2, got 2
leaves, second call: expected 2, got 4

Each line that says got something other than expected points to one bug. The first call to the leaf counter matches, and the second does not, which is the signature of a counter that is not reset.

The lab, fixed

This file has the fixed version of every function. The four buggy functions are replaced, and a test for countNodes is added. Save it as fixed.cpp:

#include <algorithm>
#include <iostream>
#include <memory>
 
struct Node {
    int value;
    std::unique_ptr<Node> left;
    std::unique_ptr<Node> right;
    explicit Node(int v) : value(v) {}
};
 
/* The tree used in every test:
         1
       /   \
      2     3
     /       \
    4         5
   /           \
  6             7
                 \
                  8
*/
std::unique_ptr<Node> buildTree() {
    auto root = std::make_unique<Node>(1);
    root->left = std::make_unique<Node>(2);
    root->right = std::make_unique<Node>(3);
    root->left->left = std::make_unique<Node>(4);
    root->left->left->left = std::make_unique<Node>(6);
    root->right->right = std::make_unique<Node>(5);
    root->right->right->right = std::make_unique<Node>(7);
    root->right->right->right->right = std::make_unique<Node>(8);
    return root;
}
 
// FIX E: the empty tree has 0 nodes.
int countNodes(const Node* n) {
    if (n == nullptr) return 0;
    return 1 + countNodes(n->left.get()) + countNodes(n->right.get());
}
 
// FIX A: the empty tree has height -1, so a leaf (height 0) comes out right.
int height(const Node* n) {
    if (n == nullptr) return -1;
    return 1 + std::max(height(n->left.get()), height(n->right.get()));
}
 
// FIX B: look at both sides.
int heightBothSides(const Node* n) {
    if (n == nullptr) return -1;
    return 1 + std::max(heightBothSides(n->left.get()), heightBothSides(n->right.get()));
}
 
// FIX C: add the right side too.
int sum(const Node* n) {
    if (n == nullptr) return 0;
    return n->value + sum(n->left.get()) + sum(n->right.get());
}
 
// FIX D: no global. Each call returns its own count, so nothing carries over.
int countLeaves(const Node* n) {
    if (n == nullptr) return 0;
    if (n->left == nullptr && n->right == nullptr) return 1;
    return countLeaves(n->left.get()) + countLeaves(n->right.get());
}
 
int main() {
    auto root = buildTree();
 
    std::cout << "nodes: expected 8, got " << countNodes(root.get()) << "\n";
    std::cout << "height: expected 4, got " << height(root.get()) << "\n";
    std::cout << "height (both sides): expected 4, got " << heightBothSides(root.get()) << "\n";
    std::cout << "sum: expected 36, got " << sum(root.get()) << "\n";
    std::cout << "leaves, first call: expected 2, got " << countLeaves(root.get()) << "\n";
    std::cout << "leaves, second call: expected 2, got " << countLeaves(root.get()) << "\n";
}

Compile and run it:

g++ -std=c++20 -Wall -o fixed fixed.cpp && ./fixed; echo "exit=$?"

The output is:

nodes: expected 8, got 8
height: expected 4, got 4
height (both sides): expected 4, got 4
sum: expected 36, got 36
leaves, first call: expected 2, got 2
leaves, second call: expected 2, got 2
exit=0

The program compiles with no warnings under -Wall, and every line matches its expected value.

Common mistakes

The five bugs above are the most common ones in tree recursion. The table below links each symptom you see to the bug it usually means. Check the first column before you read any code.

Two more points help when a bug is hard to see. First, the compiler warning -Winfinite-recursion is worth reading, even when it looks like a false alarm. The warning here was correct about the missing base case, and the crash followed. Second, a crash can hide output that was still waiting in the buffer. In the first run of a program that crashes, the lines printed before the crash may be missing. Printing with std::endl instead of "\n" flushes the buffer after each line. The following program shows that effect on a crash. It prints one line, then crashes on a node with one child. The line is printed because std::endl flushes it:

#include <iostream>
#include <memory>
 
struct Node {
    int value;
    std::unique_ptr<Node> left;
    std::unique_ptr<Node> right;
    explicit Node(int v) : value(v) {}
};
 
int countEx5(const Node* n) {
    if (n->left == nullptr && n->right == nullptr) return 1;
    return 1 + countEx5(n->left.get()) + countEx5(n->right.get());
}
 
int main() {
    Node single(1);
    std::cout << "single node: " << countEx5(&single) << std::endl;
    Node parent(1);
    parent.left = std::make_unique<Node>(2);
    std::cout << "node with one child: " << countEx5(&parent) << std::endl;
}

The output is:

single node: 1

and the exit code is 139. The second call crashes. The function checks the children of n before it checks whether n is null, so a node with one child calls itself on the missing right child, and that call reads n->left on a null pointer.

Practice

Each exercise gives you a function or a symptom. Work out the answer on paper, then read the answer below the "Show the answer" line.

1. The function below is called on the test tree. What does it print, and why?

int maxDepthEx1(const Node* n) {
    if (n == nullptr) return 0;
    return 1 + maxDepthEx1(n->left.get());
}

Show the answer

It prints 4. The function follows only left children, so it measures the left path 1, 2, 4, 6, which has 4 nodes. The longest path, 1, 3, 5, 7, 8, has 5 nodes. The fix calls the function on both children and takes the bigger answer.

2. The function below is called on the test tree. What does it print, and what is the bug?

int countEx2(const Node* n) {
    if (n == nullptr) return 1;
    return 1 + countEx2(n->left.get()) + countEx2(n->right.get());
}

Show the answer

It prints 17. Each of the 8 nodes adds 1. Each of the 9 empty child slots also adds 1, because the base case returns 1. The base case should return 0, which gives 8.

3. The function below and the code in main are run on the test tree. What do the two lines print?

int seen = 0;
 
void countEx3(const Node* n) {
    if (n == nullptr) return;
    ++seen;
    countEx3(n->left.get());
    countEx3(n->right.get());
}

main calls countEx3(root.get()) and prints seen, then calls it again and prints seen again.

Show the answer

The first line prints 8 and the second line prints 16. The counter seen is global and is never reset, so the second call adds to the first. The fix is to return the count from the function, as countLeaves does above.

4. The function below returns 5 for the test tree. Is that a bug?

int nodesOnLongestPathEx4(const Node* n) {
    if (n == nullptr) return 0;
    return 1 + std::max(nodesOnLongestPathEx4(n->left.get()), nodesOnLongestPathEx4(n->right.get()));
}

Show the answer

It is not a bug in the code, but it is the wrong answer for the height in this lesson. The function counts nodes on the longest path, which is 5. The height in this lesson counts edges, which is 4. To get the height, subtract 1 from the answer, or change the base case to return -1, as the height function does above.

5. A student writes this function and says it works on one node. It crashes on the test tree. Where is the crash?

int countEx5(const Node* n) {
    if (n->left == nullptr && n->right == nullptr) return 1;
    return 1 + countEx5(n->left.get()) + countEx5(n->right.get());
}

Show the answer

The crash is in any node that has exactly one child. The check on the first line reads the children of n, and it is only safe when n is not null. When countEx5 is called on a node with a missing right child, the second call gets a null pointer, and the first line then reads n->left on it. The fix is to return 0 for a null pointer before reading any field, as countNodes does above.

Summary

• Every recursive tree function needs a base case for the empty tree, and that check must come before any -> on the pointer.
• The value returned for the empty tree decides what the answer means. Return -1 to count edges, and return 0 to count nodes.
• A function that asks about the longest or deepest path must call itself on both children.
• A function that adds up a tree must add the result for both children, not just one.
• A global counter keeps its value between calls, so return the count from the function instead.
• Read the sanitizer report from the top, and find the line it names.