Tree terminology — root, leaf, height, depth, degree, subtree: Visual walkthrough

Step 1 — Draw a single node and ask "how tall?"

WHAT. Put one dot on the paper. Call it $v$ (just a name — think "the node we are staring at"). It has nobody below it. We want a number that answers: "How many steps down does the longest path from $v$ go before it hits the bottom?" We will call that number the height of $v$ .

WHY this question. Later, trees decide how fast algorithms run, and speed depends on the longest chain of steps. So "how many steps to the bottom" is the number worth measuring. We start with the tiniest possible tree — one dot — because you cannot understand a rule until you see its simplest case.

PICTURE. A lone dot. To go "down to the bottom" from it, you travel along edges (the lines connecting nodes). This dot has zero edges leaving downward, so the longest downward trip has length $0$ .

Figure — Tree terminology — root, leaf, height, depth, degree, subtree

Step 2 — Add ONE child and watch the height grow

WHAT. Below $v$ draw one child, call it $c$ (for child). Connect them with a single edge. Now $c$ is a leaf (no children of its own), so from Step 1, $height (c) = 0$ .

WHY. We change the picture by the smallest possible amount — one child — and simply watch what happens to the height number. This is how you discover a rule: perturb the simplest case and observe.

PICTURE. The longest trip down from $v$ now is: hop the one edge from $v$ to $c$ , then stop (because $c$ is a leaf). That trip is 1 edge long. So $height (v) = 1$ .

Look at where that $1$ came from — term by term:

$height (v) = the edge v \to c 1 + = 0, how tall c is height (c)$

The $1$ is the single edge you just walked to reach the child.
The $height (c)$ is how much further you fall once you land on $c$ .
Add them: $1 + 0 = 1$ . ✅

Step 3 — Make the child taller and re-measure

WHAT. Give $c$ its own child $g$ (a grandchild of $v$ ). Now $c$ is no longer a leaf. First measure $c$ : it has one leaf child $g$ , so by Step 2's logic $height (c) = 1 + height (g) = 1 + 0 = 1$ .

WHY. We need to see that the same rule survives when the child is itself tall. If the rule only worked for leaf children it would be useless — real trees are deep.

PICTURE. Longest trip down from $v$ : edge $v \to c$ , then edge $c \to g$ , stop. That is 2 edges. And indeed:

$height (v) = edge v \to c 1 + = 1 height (c) = 1 + 1 = 2$

The $1$ is still just the one edge from $v$ to its child.
$height (c)$ now equals $1$ because $c$ itself has a fall of one edge below it.
The whole fall from $v$ is one edge to land on $c$ plus $c$ 's own fall — the drops stack.

Step 4 — Give $v$ SEVERAL children: which one decides the height?

WHAT. Now let $v$ have three children $b$ , $c$ , $d$ with different heights below them — say $height (b) = 1$ , $height (c) = 0$ , $height (d) = 2$ . We must pick which child determines $v$ 's height.

WHY the word "longest". Height is the longest path down. If I want the longest fall from $v$ , I must dive into the child that has the deepest well beneath it. Diving into a shallow child gives a short path — that is not the height. So we need a tool that says "pick the biggest of these numbers."

PICTURE. Three wells hang below $v$ of depths $1$ , $0$ , $2$ . The deepest is $d$ 's well ( $2$ ). Walk one edge into $d$ , then fall $2$ more:

$height (v) = 1 + max (1 height (b), 0 height (c), 2 height (d)) = 1 + max (1, 0, 2) = 1 + 2 = 3$

$max (1, 0, 2) = 2$ — this selects the deepest child, here $d$ .
The $+ 1$ — the single edge from $v$ down to that chosen deepest child.
Result $3$ — the true longest fall $v \to d \to \dots \to$ bottom.

Step 5 — Assemble the general rule

WHAT. Everything above collapses into a single statement that works for any node.

WHY it's now proven, not guessed. We have a base case (Step 1: a leaf is height $0$ ) and a combining step (Steps 2–4: add one edge to the tallest child). Any node is either a leaf (base) or has children (combine). Those two cover every possible node, so the rule is complete.

This is exactly the formula the recursive machinery evaluates: it dives to the leaves, tags each with $0$ , then bubbles back up adding $1$ at every parent. See it link to real trees in Binary Trees (where each node has at most 2 children, so the $max$ is over just two numbers) and to why we cap it in Balanced Trees (AVL, Red-Black).

Step 6 — The degenerate cases (never leave a gap)

WHAT & WHY. A rule you can trust must survive weird inputs. We check the three edge cases.

Case A — empty tree (no nodes at all). There is no node to stand on, so "longest path down" has no starting point. By convention we set $height (empty tree) = - 1.$ Why $- 1$ ? So that a leaf (a node with two empty children) still computes to $0$ : $1 + max (- 1, - 1) = 1 + (- 1) = 0$ . The $- 1$ makes the empty child add nothing through the $+ 1$ . It is the value that keeps the formula honest.

Case B — a single node. It is a leaf → height $0$ (Step 1). No surprises.

Case C — a straight chain (each node has exactly one child). Every $max$ has only one thing to choose, so it just returns that child. Then $height = 1 + 1 + \dots$ once per edge — the height equals the number of edges in the chain. A chain of $n$ nodes has height $n - 1$ : this is the tallest a tree of $n$ nodes can be, the worst case that balancing exists to prevent.

Left: the empty child slots contribute $- 1$ , so a leaf stays $0$ .
Right: a chain stacks $+ 1$ per edge — no branching to shorten it.

The one-picture summary

Read the picture bottom-up: leaves are stamped $0$ ; every parent grabs the biggest child number and adds $1$ for the edge it walked; the root's number is the tree's height.

Recall Feynman retelling — say it like a story

Imagine you are standing on a node and you drop a marble down the deepest tube below you. The height is how many pipe-joints (edges) the marble clicks past before it stops.

If you are a leaf, there is no pipe below you — the marble clicks zero times. Height 0.
If you have children, the marble must first fall through one joint to reach a child (that is the $+ 1$ ), and then it keeps falling through that child's deepest tube. So you ask each child "how deep is your tube?", take the deepest one ( $max$ ), and add your one joint.
More children sideways does not help — a marble falls down one tube, so we pick the deepest, never add them up.
An imaginary "no-child" slot is scored $- 1$ so that a plain leaf still comes out to exactly $0$ .

That single " $+ 1$ for my edge, plus my deepest child's answer" is the whole formula, and it is why computing height is just recursion bubbling up from the leaves.

Quick self-test

Recall Why

$max$ and not sum in the height formula? Because a path travels down one branch at a time — the longest single path is the biggest child height, not the total. Summing would count branches you never walk together.

Recall Why does a leaf get height 0, not 1?

We count edges below the node, and a leaf has zero edges going down. Counting nodes would give a different convention; this note counts edges.

Recall Why assign height

$- 1$ to the empty tree? So a leaf (whose two children are empty) evaluates to $1 + max (- 1, - 1) = 0$ , keeping the recursion consistent.

recall::: (see cards above)

Connections

Parent: Tree terminology — this page derives its height formula.
Recursion — the base-case-plus-combine pattern is this derivation.
Binary Trees — the $max$ is over at most two children.
Balanced Trees (AVL, Red-Black) — why the tall-chain worst case matters.
Tree Traversals — the same leaves-first bubbling powers post-order traversal.
Graphs — a tree is an acyclic connected graph; "longest downward path" is a shortest-vs-longest contrast worth noting.