Debugging lab: tree recursion bugs in Python

Why this matters

Recursion means a function calls itself on a smaller part of the problem. A tree is a good fit for recursion, because each child is a smaller tree. Most tree functions are short, so a bug in one of them is often one wrong character. The difficulty is that the code looks right when you read it quickly.

Most recursion bugs fall into a few kinds. The first is a missing or wrong base case. The base case is the input where the function answers directly, without calling itself, and the recursion stops there. The second is a wrong return value: the function returns a number or a boolean that is off by one, or uses the wrong operator. The third is state that is not reset: a variable outside the function keeps its value between calls, so the second call starts from the first call's result. A fourth kind is a recursive call that does not get smaller, which ends in a RecursionError.

This lab gives six broken functions. For each one you run the program, read the symptom, find the cause, fix it and run it again. The earlier lessons in this module covered the traversal orders and the list form of trees. This lab uses only the recursion itself.

The tree we will test with

The sample tree is the same one used in the earlier lessons. Node 1 is the root. Its children are 2 and 3. Nodes 4 and 5 are the children of 2, and node 6 is the right child of 3.

        1
       / \
      2   3
     / \   \
    4   5   6

Before you run anything, write down the expected results. The sample tree has 6 nodes, a height of 2 edges, and 3 leaves (4, 5 and 6). The paths from the root to a leaf have sums 1 + 2 + 4 = 7, 1 + 2 + 5 = 8 and 1 + 3 + 6 = 10.

Writing the expected values first is the most useful habit in this lab. A bug is a gap between what you expected and what the program printed.

The support code

Every case below uses the same support code. It is a TreeNode class, a function that builds the sample tree, a function that builds a tiny tree with two nodes, and an inorder function that lists the values left, node, right. Put the support code and one broken function in a file, then run the file. The file runs one case, so you see one result or one error at a time.

Output:

inorder of the sample tree: 4 2 5 1 3 6

When an error happens inside a function, Python prints a traceback. The traceback is a list of the calls that were running when the error happened. The bottom line names the error. Each line above it shows one call, with the file name and line number, and the call that failed comes last. So read the traceback from the bottom up to find where the error happened, and then read the lines above it to see how the code got there.

Bug 1: a missing None check

The function counts the nodes in a tree. The author wrote the base case as "a leaf has no children, so return 1". That check looks at node.left and node.right, so it must run on a real node.

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
 
 
def count_nodes(node):
    if node.left is None and node.right is None:
        return 1
    return 1 + count_nodes(node.left) + count_nodes(node.right)
 
 
def tiny():
    root = TreeNode(1)
    root.left = TreeNode(2)
    return root
 
 
print("count_nodes(tiny) =", count_nodes(tiny()))

Run it. It builds a tiny tree with two nodes: 1 with a left child 2. The output is:

Traceback (most recent call last):
  File "main.py", line 20, in <module>
    print("count_nodes(tiny) =", count_nodes(tiny()))
                                 ~~~~~~~~~~~^^^^^^^^
  File "main.py", line 11, in count_nodes
    return 1 + count_nodes(node.left) + count_nodes(node.right)
                                        ~~~~~~~~~~~^^^^^^^^^^^^
  File "main.py", line 9, in count_nodes
    if node.left is None and node.right is None:
       ^^^^^^^^^
AttributeError: 'NoneType' object has no attribute 'left'

Read the traceback from the bottom. The last line says that .left was read from a None. The call above it is the one on the missing right child of node 1, which receives None. Its base case reads node.left before it checks whether node is None, and that read is the error.

The cause is that the base case only covers a leaf. A node with one child calls the function on the missing side, and that call receives None. The fix is a base case for None, which returns 0 because an empty tree has no nodes.

The fixed version prints count_nodes(tiny) = 2. The leaf check is no longer needed, because a leaf now returns 1 + 0 + 0.

Bug 2: a wrong return value

The function computes the height of a tree. Its job is to return the number of edges (the links from a parent to a child) on the longest path from the node down to a leaf.

The output is:

height(sample) = 0

The expected answer is 2. Work through the calls by hand for the sample tree. A leaf such as node 4 has two None children. Both return 0, so the maximum is 0. Node 4 returns 0, which is correct for a leaf in edges. Now node 2. Its children are 4 and 5, and both return 0. The function returns max(0, 0), which is 0. But the height of node 2 should be 1, because there is one edge from node 2 down to node 4.

The function never adds 1 for the edge from a node to its child. The result is that every node returns the height of its children, not its own height. Adding 1 fixes that. The base case also has to change. With edges, an empty tree has height -1, so a single node gives 1 + max(-1, -1), which is 0.

The fixed program prints height(sample) = 2.

Both changes are needed. If you change only the + 1, the base case of 0 gives a leaf the value 1, and the answer is one too large for every tree. If you change only the base case to -1, the answer is -1 for every tree with a node.

Bug 3: a counter that is not reset

The function counts the leaves. The author kept the running total in a global variable. A variable at the top of a file belongs to the whole program, not to one call, so its value stays between calls. A function that changes it needs the global line to do so.

The output is:

first call = 3
second call = 6

The first call is right. The second call should also return 3, because the tree has not changed, but the counter kept the value 3 from the first call and added 3 more. Each call also returns the shared total, not the leaves below its own node.

The first fix is to reset leaf_count to 0 before each use. That works, but every caller must remember to do it, and a call inside another call breaks it. The better fix is to not use a shared variable at all. Each call can return the number of leaves below its node, and the parent adds the two answers.

The fixed program prints 3 for both calls.

Bug 4: a wrong operator

The function checks whether a value is somewhere in the tree.

The output is:

contains 6 = False

The value 6 is in the tree, under node 3. The function starts at the root, which holds 1. It does not match, so it reaches the last line. The and operator means "both sides must be true". Python evaluates the left side first. The left subtree, rooted at 2, does not contain 6, so the left side is False. Python then skips the right side, because the answer of and cannot change once the left side is False. The search never reaches node 3.

Searching a tree means you need a match in either subtree. The fix is or, which is true when at least one side is true. Python also stops early in the other direction: once the left side is True, the right side is not checked.

def contains(node, target):
    if node is None:
        return False
    if node.value == target:
        return True
    return contains(node.left, target) or contains(node.right, target)

The fixed search returns True for 6.

Bug 5: a wrong base case for None

The function checks whether some path from the root to a leaf has a total equal to a target. It subtracts each node's value from the remaining amount as it goes down. At a leaf, the remaining amount must be exactly 0.

The output is:

has_path_sum(tiny, 10) = True
has_path_sum(tiny, 3) = True

The answer for a total of 10 should be False. Trace the calls. The root is 1, so remaining becomes 9. The root has a left child 2, and the call on it subtracts 2 to get 7. Node 2 is a leaf, and 7 is not 0, so that call returns False. The root also calls on its right child, which is None. The base case for None returns True, so the or on the root is True.

The base case is the bug. A None child means there is no path down that side. It should not count as a success. The fix is to return False for None. A leaf is the only place where the function should say True, and only when the remaining amount is 0.

The fixed program prints has_path_sum(tiny, 10) = False and has_path_sum(tiny, 3) = True.

Bug 6: a call that does not get smaller

The function mirrors a tree. A mirror swaps the left and right children of every node. The function swaps the children of the current node, then calls itself to mirror the subtrees.

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
 
 
def mirror(node):
    if node is None:
        return
    node.left, node.right = node.right, node.left
    mirror(node)
 
 
def sample():
    n4 = TreeNode(4)
    n5 = TreeNode(5)
    n2 = TreeNode(2)
    n2.left = n4
    n2.right = n5
    n6 = TreeNode(6)
    n3 = TreeNode(3)
    n3.right = n6
    n1 = TreeNode(1)
    n1.left = n2
    n1.right = n3
    return n1
 
 
mirror(sample())

The function swaps the children correctly, so the mistake is in the last line. It calls itself with the same node. Run it on the sample tree, and it fails. The output begins with the same line over and over, and it ends with an error:

Traceback (most recent call last):
  File "main.py", line 30, in <module>
    mirror(sample())
    ~~~~~~^^^^^^^^^^
  File "main.py", line 12, in mirror
    mirror(node)
    ~~~~~~^^^^^^
  File "main.py", line 12, in mirror
    mirror(node)
    ~~~~~~^^^^^^
  File "main.py", line 12, in mirror
    mirror(node)
    ~~~~~~^^^^^^
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

The repeated lines are the call mirror(node), with the same node each time. A recursive call should work on a smaller tree, which means a child. Here the call receives the same node, so it never reaches the base case for None. Each call is the same as the one before it, and the program keeps adding frames, one for each call that has not finished, until Python reaches its recursion limit. Then it stops with a RecursionError. The number of repeated lines depends on the Python version.

The fix is to call mirror on the two children, which are smaller trees. Swapping the children first and then calling on them works, because the children are now in their new places.

To check the result, print the tree in inorder order (left, node, right) before and after the mirror. The fixed program prints:

inorder before mirror: 4 2 5 1 3 6
inorder after mirror:  6 3 1 5 2 4

A mirror reverses the inorder order, so the second line is the first line read backward. That is a quick check you can use on any mirror function.

A method for finding a recursion bug

The six bugs have one method in common. Use these steps on any recursive tree function:

1. Run the smallest tree that shows the problem. A tree with one node, or one node and one child, often shows the bug. The tiny tree above caught bugs 1 and 5.
2. Check the base case first. Ask what the function returns for None, and for a leaf. Both answers should be right on paper before you look at the rest.
3. Trace one call with a small tree by hand. Write the value each call returns, as the height trace above does. The first wrong number shows where the bug is.
4. Look for state outside the function. A global variable that the function changes is a warning sign. Check whether a second call starts clean.
5. Check that each recursive call gets a smaller tree. The argument should be node.left or node.right, not node.
6. Run the program again after each change. Python reads the file again on every run, so an edit shows up at once. If the output does not change, check that you saved the file and ran the same file.

Common mistakes

Fixing the symptom instead of the cause

A tempting fix for bug 2 is to add if node.value == 2: return 1 to the height function. It may make one test print the right number, and it is wrong for every other tree. Always find the line that produces the wrong value, then fix that line.

Testing only with the large tree

The sample tree has six nodes, and only node 3 has one child. Bugs 1 and 5 show up only on a node with exactly one child. A test set should include a tiny tree with one child, a single node, and an empty tree.

Reading the traceback from the top

Python prints the oldest call first and the call that failed last. A reader who starts at the top sees the first call from main and may miss the failing line at the bottom. Start at the last line, which names the error, and then read the call above it. In bug 6 the repeated line is the call that never changes its argument, and it is the place to look.

Using a global variable for a result

A global variable is shared by every call and every caller. Use it only for a value that should last across calls, such as a count of all operations in the program. For a result of one function call, return the value and let the caller add it up.

Practice

Exercise 1

The function below should add up the values of all nodes. Predict what it returns for the sample tree, and explain why.

def sum_tree(node):
    if node is None:
        return 0
    return node.value

Show the answer

It returns 1. The function returns the value of the root and never looks at the children. The sum of the sample tree is 1 + 2 + 3 + 4 + 5 + 6, which is 21. The fix is return node.value + sum_tree(node.left) + sum_tree(node.right).

Exercise 2

The function below should return the number of levels in the tree, which is 3 for the sample tree. Predict what it returns for the sample tree.

def max_depth(node):
    if node is None:
        return 0
    return 1 + max_depth(node.left) + max_depth(node.right)

Show the answer

It returns 6. The + adds the depths of the two sides, so the function counts every node instead of the longest path. Each of the 6 nodes adds 1 once, which gives 6. The fix is 1 + max(max_depth(node.left), max_depth(node.right)), which returns 3.

Exercise 3

The function below should count the leaves. Predict its result for the sample tree.

def count_leaves(node):
    if node is None:
        return 0
    if node.left is None and node.right is None:
        return 0
    return count_leaves(node.left) + count_leaves(node.right)

Show the answer

It returns 0. The leaf check returns 0 instead of 1, so every leaf adds nothing to the total. The fix is to return 1 in the leaf case.

Exercise 4

The function below should return the length of the left edge chain, the number of nodes you pass going left until you reach a node with no left child. Predict what it does for the one-node tree TreeNode(9).

def left_chain_length(node):
    return 1 + left_chain_length(node.left)

Show the answer

It raises an AttributeError, with the message 'NoneType' object has no attribute 'left'. The function has no base case. For a node with no left child, the call on node.left receives None, and the next call reads .left on it. The fix is if node is None: return 0 before the return line, which gives 1 for the one-node tree.

Exercise 5

Write a function count_one_child(node) that returns the number of nodes that have exactly one child. Predict the answer for the sample tree before you run it.

Show the answer

The answer for the sample tree is 1, because only node 3 has exactly one child. The function checks each node, adds 1 when exactly one of its children is None, and adds the answers for both children. A working version is:

def count_one_child(node):
    if node is None:
        return 0
    here = 1 if (node.left is None) != (node.right is None) else 0
    return here + count_one_child(node.left) + count_one_child(node.right)

Summary

• A base case must handle None, and a leaf must return the right value. A missing None check gives an AttributeError.
• A recursive function must add the node itself to the result, and it must use or to search either side. A wrong operator or a missing + 1 gives a wrong answer with no error.
• A global counter keeps its value between calls. Return the count from each call instead of changing a shared variable.
• A call that passes the same node again never reaches the base case, which gives a RecursionError. Each recursive call should receive a child.
• Test with a single node, a node with one child, and an empty tree, and work through one call by hand before you trust the output.