Tree terminology — root, leaf, height, depth, degree, subtree: Worked examples

Two symbols we will lean on — defined before use

Before the examples, we pin down the two tools that keep reappearing, so no symbol is ever used on faith.

Formula The max-nodes bound —

derived here, not memorized Claim: a tree of height $h$ with degree $\leq d$ (where $d \geq 2$ ) holds at most $n \leq 1 + d + d^{2} + \dots + d^{h} = \frac{d ^{h + 1} - 1}{d - 1} .$ HOW we build it, level by level (WHY each factor):

Level $0$ has just the root: $1 = d^{0}$ node.
Each node on a level can father at most $d$ children, so each level is at most $d$ times as wide as the one above it. Level $1$ : at most $d^{1}$ ; level $2$ : at most $d \cdot d^{1} = d^{2}$ ; in general level $k$ holds at most $d^{k}$ nodes. That is where the powers of $d$ come from — repeated multiplication by the child-cap.
A height- $h$ tree has levels $0$ through $h$ . Summing the widest each can be: $n_{m a x} = d^{0} + d^{1} + \dots + d^{h} .$
This is a geometric series (each term is $d \times$ the previous). Its closed form is $\frac{d ^{h + 1} - 1}{d - 1}$ for $d \geq 2$ . Why this tool? The closed form lets us answer "how many nodes fit?" with one arithmetic step instead of adding $h + 1$ terms by hand.

We will use this exact result in Examples 5, 9, and 10 — always pointing back here.

The scenario matrix

Every tree question is really one of these shapes or edge cases. The examples below are tagged with the cell(s) they cover.

Cell	The scenario	Why it is tricky
C1	Normal bushy tree (multiple children per node)	The baseline — measure depth/height/degree cleanly
C2	Leaf sitting above the bottom level	Breaks the "leaf = deepest" instinct
C3	Single-node tree (root is a leaf)	Degenerate: is the root a leaf? height? depth?
C4	Empty tree ( $n = 0$ )	The ultimate degenerate — height convention flips
C5	A "stick" / path tree (every node has 1 child)	Height is maximal for its node count
C6	Perfectly balanced tree	Height is minimal — the geometric-series bound is tight
C7	Recursive height computation on an asymmetric tree	Must pick the tallest child, not the first
C8	Subtree extraction + re-measuring inside it	Depth resets to 0 inside the subtree
C9	Real-world word problem (file system)	Translate English → tree vocabulary
C10	Exam twist: given constraints, deduce a hidden number	Use $n - 1$ edges / geometric bound backwards

We now cover all ten across the worked examples. Each example names its cell(s).

Example 1 — Baseline bushy tree (C1, C2)

Worked example The tree from the parent note, re-measured carefully

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

Find: root, leaves, degree of the tree, depth of F, height of B, height of the tree.

Forecast: guess before reading — is C a leaf? What is the height of the tree?

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

Figure s01: the 8-node tree drawn top-down. Purple nodes are internal (A, B, D, G); mint nodes are leaves (C, E, F, H). Depth labels 0–3 run down the left; a coral arrow marks C as a leaf at depth 1 and traces the longest path A→D→G→H.

Root = A. Why this step? Root is the only node with no parent (parent arrow pointing into it). Look at the figure — every node has an incoming edge from above except A.
Leaves = {E, F, C, H}. Why? A leaf is defined only by "no children" — no edges leave it going downward. In the figure C has nothing below it, so it is a leaf even though it sits at depth 1 (this is cell C2). Do not tie "leaf" to "bottom row".
Degree of the tree = 3. Why? Degree of a node = its number of children. A has 3 children (B, C, D), and no node has more. The tree's degree is the maximum node degree $= 3$ .
Depth of F = 2. Why? Depth = edges on the path root → node. Path A→B→F has 2 edges. Count the edges (arrows), not the nodes.
Height of B = 1. Why? Height = edges on the longest downward path from the node to a leaf. From B we can go B→E or B→F, both 1 edge. So height $= 1$ .
Height of the tree = 3. Why? Height of the tree = height of the root = longest root-to-leaf path. A→D→G→H is 3 edges — the longest such path.

Verify: Node count $n = 8$ (A,B,C,D,E,F,G,H) ⇒ a tree must have $n - 1 = 7$ edges. Count the arrows in the figure: A-B, A-C, A-D, B-E, B-F, D-G, G-H $= 7$ . ✅ Consistent, so we drew a valid tree.

Example 2 — Single-node tree (C3, degenerate)

Figure s02: a single mint circle labelled R floating alone, with a coral note reading "root AND leaf, depth 0, height 0." No edges are drawn — there is nothing to connect.

Root = R. Why? It has no parent — it satisfies the root definition trivially.
R is also a leaf. Why? A leaf is "no children," and R has zero children. Yes — the same node is simultaneously root and leaf. There is no rule forbidding it; the two definitions look in opposite directions and both happen to be satisfied.
Degree of the tree = 0. Why? R has 0 children, and it is the only node, so the max degree is 0.
Depth of R = 0. Why? Zero edges from the root to itself.
Height of R = 0. Why? Zero edges from R down to a leaf — and R is the leaf, so the longest downward path is length 0.
Height of the tree = 0. Why? It equals the height of the root, which is 0.

Verify: $n = 1$ ⇒ edges $= n - 1 = 0$ . The picture has zero edges. ✅ And depth $_{m a x}$ $= 0 =$ height of tree, matching "height of tree = max depth."

Example 3 — Empty tree (C4, the ultimate edge case)

There is no root, no leaf, nothing to measure a path from. Why care? Recursive code hits this case: height(null) must return something so 1 + max(children) still works for a node with one missing child.
Convention: height of the empty tree $= - 1$ . Why $- 1$ ? Take the recursive rule $height (v) = 1 + max_{c} height (c)$ (the $max_{c}$ operator we defined at the top). For a single-node tree we want $height (R) = 0$ . R has no children, so we treat "the tallest child" as an empty tree of height $x$ , giving $0 = 1 + x \Rightarrow x = - 1$ . So empty $= - 1$ is exactly the value that makes the leaf formula fall out automatically.

Verify: Plug into the recursion: $height (leaf) = 1 + max (\emptyset -children) = 1 + (- 1) = 0.$ ✅ We recover leaf height 0, so $- 1$ is the self-consistent choice.

Example 4 — The "stick" tree: maximum height (C5)

Worked example Every node has exactly one child

P → Q → S → T   (P root, T leaf; each arrow is "child")

There are $n = 4$ nodes. Find: height of the tree, depth of T, degree of the tree, and confirm this is the tallest possible 4-node tree.

Forecast: for a fixed number of nodes, does a stick give the biggest or smallest height?

Figure s03: four nodes P, Q, S, T in a diagonal chain, each with exactly one child. P (top, purple) is the root; T (bottom, mint) is the sole leaf. A coral note flags "all 3 edges on ONE path, height = n-1 = 3."

Height of the tree = 3. Why? Longest root-to-leaf path P→Q→S→T has 3 edges.
Depth of T = 3. Why? Same path measured downward from root; here height and this deepest depth coincide only because it is the deepest node.
Degree of the tree = 1. Why? Every node has at most one child.
Tallest possible for $n = 4$ ? Why? Height is the number of edges on a root-to-leaf path. With $n$ nodes you have $n - 1 = 3$ edges total; a stick puts all of them on one single path, so height $= n - 1 = 3$ , the absolute maximum. You cannot make a 4-node tree taller than 3.

Verify: $n = 4 \Rightarrow$ edges $= 3$ ; the stick uses all 3 on one path, so $height = 3 = n - 1$ . ✅ Maximum confirmed.

Example 5 — Perfectly balanced tree: minimum height + geometric bound (C6)

Worked example Full binary tree of height 2

Degree $\leq 2$ everywhere, every level completely filled:

         A            level 0
       /   \
      B     C         level 1
     / \   / \
    D  E  F  G        level 2 (all leaves)

Find: $n$ , verify the geometric-series max-nodes bound, and argue this height is minimal for its node count.

Forecast: how many nodes fit in a height-2 tree of degree 2 — and does a full tree hit that maximum exactly?

Figure s04: a fully filled binary tree — A on top, B and C below, then leaves D, E, F, G. Left-edge labels show each level's capacity (lvl 0: 1, lvl 1: 2, lvl 2: 4); a coral caption states n = 1+2+4 = 7 = max for h=2, d=2.

Count nodes: $n = 7$ . Why? Level 0 has 1, level 1 has 2, level 2 has 4; $1 + 2 + 4 = 7$ .
Apply the bound $n \leq \frac{d ^{h + 1} - 1}{d - 1}$ (the one we derived in "Two symbols we will lean on") with $d = 2, h = 2$ . Why this tool and not just counting? Counting works when you can see the tree; the formula answers "what is the most a tree of this shape could hold?" — needed when you only know $d$ and $h$ . Here $d$ is the child-cap $= 2$ . $n_{m a x} = \frac{2 ^{2 + 1} - 1}{2 - 1} = \frac{8 - 1}{1} = 7.$
The full tree hits the maximum ( $7 = 7$ ). Why? "Perfectly balanced / full" means every level is completely packed, so it is the densest possible tree — equality holds.
Minimal height for $n = 7$ ? Why? Height is minimized by making each level as wide as possible. With degree 2 the widest a 7-node tree can be still needs 3 levels (heights $0, 1, 2$ ), because $1 + 2 = 3 < 7 \leq 7$ . So height 2 is the smallest achievable — you cannot fit 7 nodes into height 1 (that holds at most $\frac{2 ^{2} - 1}{1} = 3$ ).

Verify: height-1 bound $= \frac{2 ^{2} - 1}{2 - 1} = 3 < 7$ , so height 1 is impossible; height-2 bound $= 7 \geq 7$ , so height 2 is achievable and minimal. ✅ This is the shape Balanced Trees (AVL, Red-Black) chases to keep height $\approx lo g_{2} n$ .

Example 6 — Recursive height on an asymmetric tree (C7)

Worked example Pick the

tallest child, not the first

Find: the height of every node using $height (v) = 1 + max_{c} height (c)$ , computing leaves first.

Forecast: R has three children — will its height come from X, Y, or Z?

Figure s05: an asymmetric tree. Root R (purple) has children X (mint leaf), Y (purple), Z (butter). Y→W (mint leaf); Z→M (butter)→N (mint leaf). Each node is tagged with its computed height h=…; a coral arrow highlights that Z, the tallest child at h=2, sets h(R)=3.

Leaves first: $h (X) = h (W) = h (N) = 0$ . Why? No children ⇒ base case, height 0.
$h (Y) = 1 + h (W) = 1 + 0 = 1$ . Why? Y's only child W has height 0.
$h (M) = 1 + h (N) = 1 + 0 = 1$ . Why? Same base-plus-one step.
$h (Z) = 1 + h (M) = 1 + 1 = 2$ . Why? Z's child M has height 1.
$h (R) = 1 + max (h (X), h (Y), h (Z)) = 1 + max (0, 1, 2) = 1 + 2 = 3$ . Why? The $max_{c}$ operator (defined at the top) keeps the biggest child height, so the longest path leaves through the tallest child Z. If you naively took the first child X you would get 1 — wrong. The max is the whole point.

Verify: Longest root-to-leaf path is R→Z→M→N $= 3$ edges. ✅ Matches $h (R) = 3$ .

Example 7 — Subtree: depth resets inside it (C8)

Figure s06: two side-by-side pictures. Left — the full Example-6 tree with the {Z, M, N} branch coloured coral, noting "N at depth 3." Right — that same branch lifted out on its own with Z as the new local root at depth 0, so M is depth 1 and N is depth 2.

Subtree $= {Z, M, N}$ . Why? A subtree is a node plus all its descendants. Z's descendants are M (child) and N (grandchild).
Depth of N inside the subtree = 2. Why? Inside the subtree, Z becomes the local root with depth 0. Path Z→M→N has 2 edges, so N is at depth 2 relative to Z.
Depth of N in the original tree = 3. Why? From the global root R: path R→Z→M→N has 3 edges.
They differ by exactly 1. Why? The subtree view drops the single edge R→Z. In general, depth-in-subtree $=$ depth-in-original $-$ depth-of-subtree-root. Here $3 - 1 = 2$ . ✅

Verify: depth of subtree root Z in original $= 1$ (path R→Z). Then global depth of N $-$ that $= 3 - 1 = 2 =$ local depth. ✅ Depth is relative to whichever root you declare.

Example 8 — Word problem: a file system (C9)

Figure s07: rounded boxes for a file tree. Purple boxes are folders (/home, docs, pics); mint boxes are files (cv.pdf, a.jpg, b.jpg). /home branches to docs and pics; pics branches to the two jpgs. A coral arrow marks "b.jpg depth 2."

Root = /home. Why? It is the topmost container with no parent folder in this problem.
Leaves = {cv.pdf, a.jpg, b.jpg}. Why? Files contain nothing below them ⇒ no children ⇒ leaves.
Degree of the tree = 2. Why? /home has 2 children (docs, pics) and pics has 2 children (a.jpg, b.jpg). Max node degree $= 2$ .
Depth of b.jpg = 2. Why? Path /home → pics → b.jpg has 2 edges.
Height of the tree = 2. Why? Longest root-to-leaf path, e.g. /home → pics → b.jpg, is 2 edges.
Subtree rooted at pics = {pics, a.jpg, b.jpg}. Why? pics plus its descendants — a little folder-tree by itself.

Verify: $n = 6$ nodes (/home, docs, pics, cv.pdf, a.jpg, b.jpg) ⇒ edges $= 5$ . Count: home-docs, home-pics, docs-cv, pics-a, pics-b $= 5$ . ✅

Example 9 — Exam twist: deduce a hidden number (C10)

(a) Use $n - 1 = edges$ . Why this tool? Every tree obeys "edges $= n - 1$ " exactly (the parent note derived it: each non-root node contributes one parent-edge). Since it is an identity, knowing one side pins the other. Invert: $n = edges + 1 = 12 + 1 = 13$ nodes.
(b) Use the geometric max-nodes bound $n_{m a x} = \frac{d ^{h + 1} - 1}{d - 1}$ — the very formula we derived in "Two symbols we will lean on." Why this tool? We want the most nodes a bounded-degree, bounded-height tree can hold, and that is precisely the packed-every-level count that bound computes. Here the child-cap is $d = 3$ and the height is $h = 2$ : $n_{m a x} = \frac{3 ^{2 + 1} - 1}{3 - 1} = \frac{3 ^{3} - 1}{2} = \frac{27 - 1}{2} = \frac{26}{2} = 13.$ What each piece means: $3^{3} = 27$ is "if every one of the $h + 1 = 3$ levels were as wide as the child-cap allows"; subtracting $1$ and dividing by $d - 1 = 2$ is just the geometric-series shortcut for $3^{0} + 3^{1} + 3^{2}$ .
(b) Cross-check by adding the levels directly: level 0 holds $3^{0} = 1$ , level 1 holds $3^{1} = 3$ , level 2 holds $3^{2} = 9$ ; total $1 + 3 + 9 = 13$ . ✅ Same answer, so the closed form and the hand-sum agree.

Verify: (a) $13 - 1 = 12$ edges ✅. (b) $\frac{3 ^{3} - 1}{3 - 1} = 13$ and $1 + 3 + 9 = 13$ ✅.

Example 10 — Limiting behaviour: stick vs balanced as $n$ grows (C5 vs C6 combined)

Stick height $= n - 1 = 6$ . Why? All 6 edges lie on one path (Example 4's logic scaled to 7 nodes).
Balanced height $= 2$ . Why? From Example 5, a full degree-2 tree with 7 nodes packs 3 levels ⇒ height 2. Formally, height $\approx ⌊ lo g_{2} n ⌋ = ⌊ lo g_{2} 7 ⌋ = 2$ .
The gap is $6 - 2 = 4$ edges, and it widens as $n$ grows: stick height grows linearly ( $n - 1$ ) while balanced grows logarithmically ( $\approx lo g_{2} n$ ). Why care? Search cost in Binary Search Trees is proportional to height — this gap is the entire reason Balanced Trees (AVL, Red-Black) exist.

Verify: $n = 7$ : stick $= 7 - 1 = 6$ ; balanced $= ⌊ lo g_{2} 7 ⌋ = 2$ ; gap $= 4$ . ✅

Recall Self-test: name the cell, then answer

A node with no children sitting at depth 1 — is it a leaf? ::: Yes (cell C2). Leaf = no children, at any depth. Height of a tree containing one node? ::: 0 (cell C3). Zero edges below the root. Height of the empty tree, and why? ::: $- 1$ (cell C4), so that $1 + (- 1) = 0$ gives leaf height 0. For fixed $n$ , which shape maximizes height? ::: The stick (cell C5); height $= n - 1$ . Max nodes in a degree-2 tree of height 3? ::: $\frac{2 ^{4} - 1}{2 - 1} = 15$ (cell C6/C10). Depth of a node inside a subtree vs whole tree? ::: Subtree depth $=$ global depth $-$ depth of subtree root (cell C8).

Connections

Back to the parent terminology note
Binary Trees — the degree- $\leq 2$ special case behind Examples 5, 10.
Binary Search Trees — search cost $\propto$ height (Example 10's punchline).
Balanced Trees (AVL, Red-Black) — engineer height down to $\approx lo g_{2} n$ .
Tree Traversals — visiting the nodes we just measured.
Recursion — the height formula in Examples 6–7 is pure recursion.
Graphs — trees are acyclic connected graphs; degree conventions differ.

Worked examples — Tree terminology — root, leaf, height, depth, degree, subtree