Measuring Height

Height is the first measurement that depends on the tree’s shape, not only on how many nodes it has. It is defined in terms of paths.

A path is a sequence of nodes in which each one is a child of the one before. In our tree, 3, 5, 1 is a path, and so is 3, 8:

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

The height of a tree is the number of edges on the longest path from the root down to a leaf. We count edges, the steps between nodes, not the nodes themselves.

From the root, two paths reach a leaf. The path to 8 takes one step, and the path through 5 down to 1 takes two. The longest is two edges, so the tree’s height is 2.

The longest path down from a node has to go through one of its two children and keep going from there. So a node’s height is one, the edge down to a child, plus the height of whichever subtree is taller:

height(node) = 1 + max(height(left), height(right))

What about the base case, the empty tree? A leaf has nothing below it, so its height should be 0. A leaf’s two children are both empty, so the formula says height(leaf) = 1 + max(height(empty), height(empty)). For that to come out to 0, height(empty) must be -1. So we define the empty tree to have height -1.

public static <T> int height(Node<T> node) {
  if (node == null) {
    return -1;  // base case: an empty tree has height -1
  }
  return 1 + Math.max(height(node.left), height(node.right));
}

The recursion forms the same call tree we saw for size. Only the combining step is different: size adds the two subtrees because every node counts, and height keeps the larger one. On our tree, each leaf returns 0, height(5) is 1 + max(0, -1) = 1, and height(3) is 1 + max(1, 0) = 2.