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

This page builds every symbol and word the parent note uses, starting from "what is a dot and a line". If the parent note said "node" or "edge" or wrote $n-1$ without showing you the picture — we fix that here, from zero.

Symbol 0 — the dot (node) and the line (edge)

Before any tree, we need two things you can literally draw.

Figure s01 (below) defines node and edge visually: it shows two labelled circles (A, B) joined by one orange line, with the dot and the line each arrow-labelled so you can attach the word to the picture before reading on.

WHY start here? Every later word — parent, child, root, leaf — is defined by which dots connect to which. If "node" and "edge" aren't concrete pictures first, none of the later words can be.

Symbol 1 — direction: parent and child

A plain line just says "connected". A tree needs a direction: one dot is above, the other below.

WHY the topic needs it: words like ancestor ("dots above you") and descendant ("dots below you") are meaningless without an agreed up/down. Parent/child is that agreement.

Symbol 2 — the special dot: root

Figure s02 (below) defines the root visually and pins down "up" versus "down": the red circle R at the top has only downward lines, and green/blue arrows label the two directions we will measure with (up toward the root, down toward the branches).

WHY exactly one? A tree is a single hierarchy — one boss. If two dots had no parent, you'd have two separate trees, not one. The root is the anchor from which "up" is measured.

Symbol 3 — the childless dot: leaf

Now that "child" exists (Symbol 1), we can name the dots that have none.

WHY the topic needs it: the parent's height definition and the sentence "leaf has height 0" are meaningless until "leaf" is a defined word. We define it before height uses it.

Symbol 4 — the forbidden thing: cycles (no loops)

Figure s03 (below) contrasts a valid loop-free tree (green, left) against a forbidden shape with a cycle (red, right), where dot D can be reached from R two different ways. Compare the two panels: the loop is the only difference.

WHY the topic needs it: the rule "no one can be their own ancestor" is exactly "no cycles". It is the property that separates a tree from a general graph.

Symbol 5 — the count $n$ and the number of edges

Now we can read the parent's first formula.

WHY $n-1$, shown from the picture: every dot except the root has exactly one line going up to its parent (Symbol 1 + Symbol 2). That is one edge per non-root dot. There are $n$ dots total and $1$ root, so $n-1$ non-root dots, hence $n-1$ edges. The root adds none — it has no parent line. This is counted, not memorised.

$\underset{\text{all dots}}{\underbrace{n}}-\underset{\text{the root}}{\underbrace{1}}=\underset{\text{edges}}{\underbrace{n-1}}$

Symbol 6 — counting distance in edges, then depth and height

Every "how far" measurement in this topic counts edges along a path, never dots.

With "path length = edges" fixed, the two measurements the parent uses become precise:

WHY the topic needs both: the parent's recursive formula (next section) computes $\text{height}(v)$, and its count bound uses the tree's height $h=\text{height}(\text{root})$. Neither is meaningful until these two words are pinned to path length.

Symbol 7 — degree of a node, and degree $d$ of the tree

WHY the topic needs it: the parent writes "degree $\le d$" in its count formula. That $d$ is precisely this tree-wide maximum, so the count bound is a guaranteed ceiling, not just a typical case.

Symbol 8 — subtree

WHY the topic needs it: the recursive height formula treats each child as the root of its own subtree and asks for that subtree's height. Without "subtree" the recursion has nothing to recurse on.

Symbol 9 — the recursive height formula (base case + step)

The parent's formula uses two pieces of notation you must own:

$\text{height}(v)=1+{\max }_{c\in \text{children}(v)}\text{height}(c)$

Symbol 10 — powers and the geometric-series bound

The parent claims $n\le 1+d+d^2+\cdots +d^h=\frac{d^{h+1}-1}{d-1}$.

Now the closed form is derived, not asserted:

How these foundations feed the topic

Read the map below bottom-up: node and edge (top boxes) are the raw dots and lines. Adding a direction gives parent/child, which lets us name the root (childless-above) and leaf (childless-below). "No cycles" plus the root gives the $n-1$ edge count. Counting in edges gives depth and height; the set of children plus $\max$ gives the recursive height formula (grounded by the leaf base case). Degree per node, maxed into the tree degree $d$, plus powers, gives the geometric-series bound. All arrows converge on the Tree Terminology topic.

Equipment checklist

Connections

• Tree Terminology — root, leaf, height, depth, degree, subtree (Hinglish) — the parent topic these foundations feed.
• Recursion — height and subtree are defined in terms of themselves (base case + combining step).
• Graphs — a tree is a connected graph with no cycles; compare the degree definitions.
• Binary Trees — the special case where degree $\le 2$.
• Binary Search Trees — adds an ordering rule on top of this vocabulary.
• Tree Traversals — walk nodes using depth and level.
• Balanced Trees (AVL, Red-Black) — control height using the count bound above.