Counting the Nodes

The simplest thing to ask about a tree is how many nodes it holds. Here is the tree we built in the previous section.

       ╭───╮
       │ 3 │
       ╰─┬─╯
    ┌────┴────┐
  ╭─┴─╮     ╭─┴─╮
  │ 5 │     │ 8 │
  ╰─┬─╯     ╰───╯
  ┌─┘
╭─┴─╮
│ 1 │
╰───╯

It has four nodes, and we can count them by eye. But we want a method that counts the nodes of any tree, so we think recursively.

A tree is a node with a left subtree and a right subtree below it. Suppose size(node.left) and size(node.right) already return the correct counts, the same assumption we made for factorial(n - 1). Then the count of the whole tree is one for the node itself, plus the count of the left subtree, plus the count of the right.

On our tree, the left subtree, rooted at 5, holds two nodes, and the right subtree, rooted at 8, holds one. Add the node 3 itself, and the total is 4. And how did we know the subtree at 5 holds two? The same way: one for 5, plus its left subtree (the single node 1) and its right subtree (empty).

The recursion stops at the empty tree, a null reference. It has no nodes, so its count is 0. Here is the method:

public static <T> int size(Node<T> node) {
  if (node == null) {
    return 0;  // base case: an empty tree has no nodes
  }
  return 1 + size(node.left) + size(node.right);  // this node, plus each subtree
}

The shape of the call tree

When we run size on the root, the calls form a call tree, the same kind we drew earlier in this chapter. If we keep only the calls whose argument is not null, and label each call by the value in its node, we get this:

     size(3)=4
    ┌────┴─────┐
size(5)=2  size(8)=1
    │
size(1)=1

This call tree has the same shape as the tree itself. Earlier we saw that a method making two recursive calls has a call tree that branches in two. size makes its two calls on node.left and node.right, the two subtrees, so at every node the call tree branches exactly where the tree branches.

The calls left out, such as the one on the right child of 5, receive null and return 0 right away.

This is the pattern for measuring a whole tree: handle the empty tree directly, then build a node’s answer out of the answers from its two subtrees.