Tree terminology — root, leaf, height, depth, degree, subtree: Exercises

The two reference trees for this page:

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

Definition Tree

T (used in L1–L3), drawn above-left

           A          depth 0
         / | \
        B  C  D       depth 1
       / \     \
      E   F     G     depth 2
                 \
                  H   depth 3

Definition Tree

U (used in L4–L5), drawn above-right

             R            depth 0
           /   \
          P     Q         depth 1
         /|    / \
        S T   X   Y       depth 2
             /
            Z             depth 3

Level 1 — Recognition

Read the definition straight off the picture. No computation.

Recall Solution L1.1

WHAT we look for: root = the only node with no parent (the topmost). Leaf = a node with no children.

Root $= A$ . It is the only node nobody points down to.
Leaves $= {E, F, C, H}$ . Each has zero downward edges. Note $C$ is a leaf even though it sits at depth $1$ — leaf means "no children", not "deepest".

Recall Solution L1.2

Children of $A$ = the nodes one edge below $A$ = ${B, C, D}$ . Siblings = nodes sharing the same parent. E.g. $E$ and $F$ (both children of $B$ ); or $B, C, D$ (all children of $A$ ).

Recall Solution L1.3

True. Internal node = "has at least one child". $G$ has child $H$ , so $G$ is internal (not a leaf).

Level 2 — Application

Now you must count edges or apply a formula.

Recall Solution L2.1

Depth = number of edges on the path from the root down to the node. Count edges, not nodes.

Path to $H$ : $A \to D \to G \to H$ = 3 edges → depth $3$ .
Path to $C$ : $A \to C$ = 1 edge → depth $1$ .

Recall Solution L2.2

Height = edges on the longest path from the node down to a leaf.

From $D$ : $D \to G \to H$ = 2 edges → height $2$ . Degree = number of children.
$A$ has children ${B, C, D}$ → degree $3$ .

Recall Solution L2.3

WHY the rule: every node except the root is joined to its parent by exactly one edge. That is one edge per non-root node. $edges = n - 1 = 47 - 1 = 46.$

Level 3 — Analysis

Combine several definitions or run the recursive height algorithm.

Recall Solution L3.1

WHAT we do: start from leaves (base case) and build upward, because a node's height depends on its children's heights.

Leaves: $h (E) = h (F) = h (C) = h (H) = 0$ .
$h (G) = 1 + h (H) = 1$ .
$h (B) = 1 + max (h (E), h (F)) = 1 + 0 = 1$ .
$h (D) = 1 + h (G) = 1 + 1 = 2$ .
$h (A) = 1 + max (h (B), h (C), h (D)) = 1 + max (1, 0, 2) = 3$ .

Height of the whole tree = height of the root $A = 3$ . ✅

Recall Solution L3.2

Subtree rooted at $B$ = $B$ plus all its descendants = ${B, E, F}$ , with $B$ as its own local root. Degree of a (sub)tree = the max degree of any node in it. Here $B$ has $2$ children, $E$ and $F$ have $0$ . Max $= 2$ → degree $2$ .

Recall Solution L3.3

Ancestor = any node on the path from $H$ up to the root (excluding $H$ itself).

Ancestors of $H$ : $G, D, A$ . Descendant = any node below the given node.
Descendants of $A$ = everyone except $A$ = ${B, C, D, E, F, G, H}$ (all $7$ other nodes, since $A$ is the root).

Level 4 — Synthesis

Build or reason about a whole structure, using tree U.

Recall Solution L4.1

Bottom-up, leaf $= 0$ :

Leaves: $h (S) = h (T) = h (Z) = h (Y) = 0$ .
$h (X) = 1 + h (Z) = 1$ .
$h (P) = 1 + max (h (S), h (T)) = 1$ .
$h (Q) = 1 + max (h (X), h (Y)) = 1 + max (1, 0) = 2$ .
$h (R) = 1 + max (h (P), h (Q)) = 1 + max (1, 2) = 3$ .

Tree height $= h (R) = 3$ . Subtree sizes: subtree( $R$ ) $= 8$ (all nodes), subtree( $Q$ ) $= {Q, X, Y, Z} = 4$ , subtree( $P$ ) $= {P, S, T} = 3$ . Excluding the root, the largest subtree is rooted at $Q$ with $4$ nodes.

Recall Solution L4.2

With $d = 2$ , $h = 3$ : $n_{m a x} = \frac{2 ^{3 + 1} - 1}{2 - 1} = \frac{16 - 1}{1} = 15.$ Tree U has $n = 8 \leq 15$ ✅. WHY the slack: the bound assumes every level is completely full ( $2^{0} + 2^{1} + 2^{2} + 2^{3} = 1 + 2 + 4 + 8 = 15$ ). Tree U is not full — level 2 has only 3 of a possible 4 nodes and level 3 has only 1 of a possible 8 — so it holds far fewer than the max. The bound is a ceiling, not an exact count.

Recall Solution L4.3

Strategy: to minimise height with a child-cap of $d = 2$ , pack each level as full as possible (each node grabs its $2$ children before we open a new level).

Level 0: $1$ node (root) → running total $1$ .
Level 1: $2$ nodes → total $3$ .
Level 2: up to $4$ nodes, but we only need $6 - 3 = 3$ more → total $6$ . We stop at level 2, so height $= 2$ . One valid shape:

        a          depth 0
       / \
      b   c        depth 1
     / \  /
    d  e f         depth 2

Any arrangement filling level 1 fully then partially filling level 2 works — height $2$ is optimal because $3$ nodes ( $1 + 2$ ) is the most that fit in heights $0$ – $1$ , and $6 > 3$ forces at least one more level.

Level 5 — Mastery

Prove small general facts. Answers are formulas/arguments, not single trees.

Recall Solution L5.1

Definitions used: leaf = degree $0$ ; internal = degree $\geq 1$ . Every node has a degree (a child-count) that is either $0$ or $\geq 1$ — never both, never neither. So each node lands in exactly one of the two buckets. A partition of the $n$ nodes into two disjoint groups sums to $n$ : $# leaves + # internal = n .$ No overlap, because " $= 0$ " and " $\geq 1$ " cannot hold simultaneously. $■$

Recall Solution L5.2

Count edges two ways.

From the parent side: each internal node contributes exactly $2$ downward edges, so total edges $= 2 I$ .
From the child side: every node except the root has exactly one edge to its parent, so total edges $= n - 1 = (L + I) - 1$ .

Set them equal: $2 I = L + I - 1 \Rightarrow I = L - 1 \Rightarrow L = I + 1. ■$ Sanity check on tree U (which is not full, so this need not hold — good to see): it fails, confirming the "full" hypothesis is essential. A full example: root with two leaf children → $I = 1, L = 2 = I + 1$ ✅.

Recall Solution L5.3

Level-by-level bound. Put the root on level $0$ . A node on level $k$ has at most $d$ children, each on level $k + 1$ . So:

level $0$ : at most $1 = d^{0}$ node,
level $1$ : at most $d^{0} \cdot d = d^{1}$ ,
level $k$ : at most $d^{k}$ (each level multiplies the previous max by $d$ ).

Height $h$ means the deepest level is $h$ . Summing all levels $0$ to $h$ gives a geometric series — chosen precisely because each term is $d \times$ the one before: $n \leq \sum_{k = 0}^{h} d^{k} = \frac{d ^{h + 1} - 1}{d - 1} .$ Equality holds exactly when every level is completely full — i.e. a perfect $d$ -ary tree where every internal node has all $d$ children and every leaf sits on level $h$ . $■$

Recall One-line self-test (hide, then recall)

Depth ::: edges up to the root; root $= 0$ . Height ::: edges down to the deepest leaf; leaf $= 0$ . Edges in an $n$ -node tree ::: $n - 1$ . Recursive height ::: $1 + max$ of children's heights. Full binary tree leaves vs internals ::: $L = I + 1$ . Max nodes, height $h$ , degree $\leq d$ ::: $\frac{d ^{h + 1} - 1}{d - 1}$ .

Connections

Binary Trees — L4/L5 use the degree- $\leq 2$ special case directly.
Recursion — the height algorithm and L5 proofs are recursive/inductive.
Balanced Trees (AVL, Red-Black) — the height bound in L5.3 is why balancing gives $O (lo g n)$ .
Tree Traversals — visiting by depth/level.
Graphs — the "count edges two ways" trick in L5.2 is a classic graph argument.

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