Sums, the smallest value and depth

Most algorithms on trees have the same shape as count_nodes: an answer for the empty tree, and for any other tree, this node's value combined with the answers for its two subtrees. Here is a tree with a negative number in it:

         7
       /   \
      2     9
     /     / \
   -4     5   12
           \
            6

The sum of its values is this node's value plus the sums of the two subtrees. An empty tree adds nothing. The depth of a tree, also called its height, is the number of nodes on the longest path from the root down to a leaf. An empty tree has depth 0, and any other tree is one level deeper than the deeper of its two subtrees:

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


def tree_sum(node):
    if node is None:
        return 0
    return node.value + tree_sum(node.left) + tree_sum(node.right)


def depth(node):
    if node is None:
        return 0
    return 1 + max(depth(node.left), depth(node.right))


tree = Node(7, Node(2, Node(-4)), Node(9, Node(5, None, Node(6)), Node(12)))
print(tree_sum(tree))
print(depth(tree))
print(depth(tree.left))

37
4
2

The longest path is 7, 9, 5, 6: four nodes. The left subtree, 2 with its child -4, has depth 2.

When the empty tree has no good answer

What's the smallest value of an empty tree? There's no good answer. If the base case returned 0, a tree with only positive numbers would get 0 as its smallest value, which is wrong. For questions like this, assume the tree isn't empty, start from the node's own value, and compare it with the answer for each subtree that exists:

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


def smallest(node):
    result = node.value
    if node.left is not None:
        result = min(result, smallest(node.left))
    if node.right is not None:
        result = min(result, smallest(node.right))
    return result


tree = Node(7, Node(2, Node(-4)), Node(9, Node(5, None, Node(6)), Node(12)))
print(smallest(tree))
print(smallest(tree.right))

-4
5

Here the base case is a leaf: neither if is true, so the leaf returns its own value without calling the function again.

The recipe

To write a recursive function for a tree, answer two questions. What is the answer for the smallest tree, an empty one or a leaf? And if you already had the answers for the two subtrees, how would you get the answer for the whole tree? The recursive calls give you those answers, so you only need to combine them.