What is the height of a node and of a tree, and how is it computed?

The height of a leaf is 0; the height of an internal node is 1 + the maximum height of its children. The height of a tree is the height of its root, which equals the depth of its deepest node.

* Depth is measured down from the root; height is measured up from the deepest leaf below. *

Height is the mirror image of depth: depth asks "how far am I from the top?", height asks "how far is it from me down to the bottom?". Written as a recursive algorithm:

Algorithm height(T, v)
  h = 0
  for all children w of v
    h = max(h, 1 + height(T, w))
  return h

A leaf has no children, so the loop never runs and it returns 0, the base case. An internal node asks each child for its height and keeps the largest, plus one for the edge down to that child.

Intuitively, the height of a tree is its number of levels minus one. It matters because many tree operations take time proportional to the height, so a tree of $n$ nodes that is short and bushy (height about $\log n$) is far faster to work with than one that has degenerated into a chain (height $n - 1$).

Computing the height of the root this way visits every node once: $O(n)$.

Go deeper:

• Tree (data structure) — terminology — depth, height, level and the other vocabulary, with the edge-counting convention.