Tree Terminology and Properties

Why Trees? The Shape of Hierarchy

Up to this chapter we have worked with structures that are essentially linear: arrays, linked lists, stacks, queues. Each element has at most one predecessor and one successor. Linearity is powerful, but the world is not flat. The folders on your computer, the replies under a forum post, the pages reachable from a homepage, the executives reporting to a CEO, the syntactic structure of a sentence, the state of a chess game several moves ahead — none of these are lines. They branch.

A tree is the data structure that captures branching hierarchy. One designated element — the root — sits at the top, every other element has exactly one immediate ancestor, and there are no cycles. That single restriction (one parent per element, no cycles) is what makes trees enormously useful: it lets us traverse, search, summarize, and modify hierarchies in time proportional to $O(\log n)$ when the tree is balanced, and never worse than $O(n)$ in the worst case.

Intuition. If a linked list is a chain, a tree is a family tree. Every person has exactly one biological mother in the diagram, but a mother can have many children. Pick any person; trace upward and you eventually reach the original ancestor. There are no loops — you cannot be your own great-grandparent.

Before any formal definition, here are the everyday hierarchies that trees model in production software. Notice that the "branching factor" differs wildly — sometimes 2, sometimes thousands — and the depth differs too:

Understanding tree terminology is therefore not just bookkeeping. It is the vocabulary you will use every time you ship a feature that touches a file system, a UI tree, a configuration document, a routing table, a version-control history, a database index, or a machine-learning model of class hierarchies. The rest of this chapter, and most of the next five chapters, will be unintelligible without it.

A Formal Definition

A tree is a finite set $T$ of nodes such that:

1. Either $T = \emptyset$ (the tree is empty),
2. Or there is a designated node $r \in T$, called the root, and the remaining nodes $T \setminus \{r\}$ are partitioned into $k \geq 0$ disjoint subsets $T_1, T_2, \dots, T_k$, each of which is itself a tree, called a subtree of $r$.

The recursive flavor is the point. The definition says a tree is either empty, or a root attached to a list of trees. That single sentence is what makes nearly every tree algorithm in this book a few lines of recursion: a function that handles the empty case and the "root plus subtrees" case is, by induction, a function that handles every tree.

An equivalent graph-theoretic definition is sometimes more useful: a tree is an undirected graph that is connected and acyclic. In a connected graph there is a path between every pair of vertices; in an acyclic graph there is no closed loop. A tree of $n$ nodes therefore has exactly $n - 1$ edges — one fewer than the number of nodes — because every node except the root contributes exactly one edge to its parent.

Core Terminology, Visualized

The visualizer below shows a single tree of $n = 11$ nodes. Click any node to see all of the relationships defined in this section colored simultaneously. Each definition will refer back to the same picture, so you can read with one hand on the slider.

With that picture in mind, here is the terminology, in the order you will use it most often:

• Root. The unique node with no parent. In our example the root is $A$. A non-empty tree has exactly one root.
• Parent and child. If $u$ is immediately above $v$ in the tree, then $u$ is the parent of $v$, and $v$ is a child of $u$. Every non-root node has exactly one parent. $B$ is a parent of $E$ and $F$.
• Sibling. Two nodes are siblings if they share the same parent. $E$ and $F$ are siblings; so are $H, I, J$.
• Leaf (or external node). A node with no children. In our example the leaves are $E, F, K, H, I, J$. Leaves carry the "data" in many trees: file contents in a file system, text nodes in the DOM, predicted classes in a decision tree.
• Internal node. Any non-leaf node. In our example $A, B, C, D, G$ are internal. Internal nodes carry structure (the directories, the elements, the questions); leaves carry content.
• Edge. The connection between a parent and one of its children. A tree with $n$ nodes has exactly $n - 1$ edges — we will prove this in a moment.
• Path. A sequence of nodes $v_0, v_1, \dots, v_k$ in which each consecutive pair is connected by an edge. In a tree there is exactly one path between any two nodes — another consequence of being connected and acyclic.
• Ancestor and descendant. If the unique path from $v$ upward to the root passes through $u$, then $u$ is an ancestor of $v$, and $v$ is a descendant of $u$. Every node is its own ancestor and its own descendant by convention (these are the "improper" cases). Click $K$ in the visualizer: its ancestors are $G, C, A$.
• Subtree. The subtree rooted at $v$ is $v$ together with all of its descendants. The subtree at $D$ consists of $\{D, H, I, J\}$. Subtrees are the recursive handle on a tree: every algorithm of the form "do something to a tree" is, almost always, "do something to the root, then recurse on each subtree."

Depth, Height, Level, Degree

Five numbers are attached to every tree and every node. They look similar at first glance, but they measure different things, and mixing them up is the most common bug in undergraduate tree code.

Three short, important identities follow directly from the table:

1. Root has depth 0. The path from the root to itself has zero edges. So $\text{depth}(\text{root}) = 0$.
2. Leaf has height 0. The longest downward path from a leaf is the empty path, which has zero edges. So $\text{height}(\text{leaf}) = 0$.
3. Tree height is bounded by node count. $\text{height}(T) \leq n - 1$, with equality when the tree is a single chain (a "stick").

Mathematical Properties of Trees

Three properties are worth proving once, in full, because every later chapter quietly assumes them. They are simple, but they are the reason balanced search trees, heaps, segment trees, and tries can promise $O(\log n)$ operations.

1. A tree on n nodes has exactly n − 1 edges.

Every node except the root contributes exactly one edge to its parent. The root contributes none. So the total number of edges equals the number of non-root nodes, which is $n - 1$. As a corollary, if you ever count $n$ edges in something you are calling a tree, you have either miscounted or it is not a tree (it has a cycle, or a node with two parents).

2. The unique-path property.

Between any two nodes $u, v$ there is exactly one path. If there were two distinct paths, joining them would form a cycle, contradicting acyclicity; if there were none, the tree would not be connected. This is what allows ancestor/descendant relationships to be well-defined: there is no ambiguity about "the" path from a node to the root.

3. Height is between log₂ n and n − 1.

For a binary tree (every internal node has at most 2 children), the number of nodes at depth $d$ is at most $2^d$. Summing over depths $0, 1, \dots, h$ gives at most $2^{h+1} - 1$ nodes total, so $n \leq 2^{h+1} - 1$, which rearranges to $h \geq \lceil \log_2 (n + 1) \rceil - 1$. On the other extreme, a tree shaped like a chain has $h = n - 1$. So:

$\lceil \log_2(n+1) \rceil - 1 \;\leq\; h \;\leq\; n - 1$

The whole story of balanced binary trees (AVL, red-black, B-trees) is the story of forcing the height to stay near the lower bound. We will explore that in Chapter 13. For now, slide $n$ below to feel the spread:

Notice how at $n = 64$ the balanced height is $6$ while the worst-case stick height is $63$. That ten-times-shorter path is the difference between an instant search and a sluggish one, and it is why the rest of this book cares so much about keeping trees balanced.

Kinds of Trees You Will Meet

The same word "tree" describes many shapes with very different properties. Knowing the names lets you communicate precisely with other engineers and pick the right algorithm.

We will spend chapters on each of these. For this section the only thing to internalize is that they are all trees — the terminology in this section applies to every one of them — but each one piles extra invariants on top to make a particular operation cheap.

A Tree Node in C

Now let us encode a tree in actual code. We start with C because in C the memory layout of a tree is visible to the eye: a node is a struct with payload data and pointers to other structs. The pointer is the edge.

For a general tree (any number of children), the cleanest layout is the first-child / next-sibling representation: each node stores one pointer to its leftmost child and one pointer to the next sibling on its right. This handles arbitrary fan-out in two pointers per node, no dynamic arrays required.

Other recursive types follow the same shape: a linked list (one next pointer), a doubly-linked list (next + prev), or a binary tree (left + right).

Tree fragment: B has children E and F. Then B->child = E, E->sibling = F, F->sibling = NULL.

Owners must remember to call free_tree() exactly once on every node they allocate, or you leak memory. Valgrind / AddressSanitizer will catch the mistake in CI.

Adding [B, C, D] to A: first call sets A->child = B; second walks B and sets B->sibling = C; third walks B->C and sets C->sibling = D.

If parent already has [E, F] and we add G: s = E -> F (since F->sibling is NULL we stop) -> F->sibling = G.

On A: free_tree(B-subtree) -> free_tree(C-subtree) -> free_tree(D-subtree) -> free(A).

After these calls: A->child = B, B->sibling = C, C->sibling = D, D->sibling = NULL.

1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5/* A node in a general tree. The "first-child / next-sibling" layout
6   represents arbitrary fan-out using only two pointers per node. */
7typedef struct TreeNode {
8    char label;                  /* node payload (a single char for the demo) */
9    struct TreeNode *child;      /* leftmost child, or NULL if leaf */
10    struct TreeNode *sibling;    /* next sibling to the right, or NULL */
11} TreeNode;
12
13/* Allocate a new node with the given label and no children. */
14TreeNode *new_node(char label) {
15    TreeNode *n = (TreeNode *) malloc(sizeof(TreeNode));
16    if (n == NULL) {
17        fprintf(stderr, "out of memory\n");
18        exit(1);
19    }
20    n->label   = label;
21    n->child   = NULL;
22    n->sibling = NULL;
23    return n;
24}
25
26/* Append a child to the end of parent's child list.
27   Cost: O(k) where k is the current number of children of parent. */
28void add_child(TreeNode *parent, TreeNode *child) {
29    if (parent->child == NULL) {
30        parent->child = child;
31    } else {
32        TreeNode *s = parent->child;
33        while (s->sibling != NULL) {
34            s = s->sibling;
35        }
36        s->sibling = child;
37    }
38}
39
40/* Recursively free the entire subtree rooted at n. Post-order:
41   children first, then the node itself. */
42void free_tree(TreeNode *n) {
43    if (n == NULL) return;
44    free_tree(n->child);
45    free_tree(n->sibling);
46    free(n);
47}
48
49int main(void) {
50    /* Build the tree from the visualizer:
51              A
52            / | \
53           B  C  D
54          /|  |  /|\
55         E F  G H I J
56              |
57              K
58    */
59    TreeNode *A = new_node('A');
60    TreeNode *B = new_node('B');
61    TreeNode *C = new_node('C');
62    TreeNode *D = new_node('D');
63    add_child(A, B); add_child(A, C); add_child(A, D);
64
65    add_child(B, new_node('E'));
66    add_child(B, new_node('F'));
67
68    TreeNode *G = new_node('G');
69    add_child(C, G);
70    add_child(G, new_node('K'));
71
72    add_child(D, new_node('H'));
73    add_child(D, new_node('I'));
74    add_child(D, new_node('J'));
75
76    free_tree(A);
77    return 0;
78}

The Same Tree in Python

Python hides pointers behind the garbage collector and lets us write the same structure as a small class. The semantics are identical (a node holds references to its children) but the lifetime is managed for us, and the algorithms are easier to read because the syntax is closer to the math.

Without default_factory: TreeNode('A').children is TreeNode('B').children would be True. With default_factory it is False.

After add_child calls in build_demo_tree, A.children == [B, C, D] in that order. A.children[0] is B.

In a multithreaded context (rare for raw Python) the order also avoids a brief window where the child is in its parent's list but does not yet know its own parent.

Leaves of build_demo_tree(): E, F, K, H, I, J — exactly the nodes for which is_leaf() is True.

Output:\n  root label: A\n  root degree: 3\n  first leaf under B: E

1from __future__ import annotations
2from dataclasses import dataclass, field
3from typing import List, Optional
4
5
6@dataclass
7class TreeNode:
8    """A node in a general (multi-way) tree."""
9    label: str
10    children: List["TreeNode"] = field(default_factory=list)
11    parent: Optional["TreeNode"] = None  # filled in by add_child
12
13    def add_child(self, child: "TreeNode") -> "TreeNode":
14        """Attach child as the rightmost child of self. Returns child."""
15        child.parent = self
16        self.children.append(child)
17        return child
18
19    def is_leaf(self) -> bool:
20        return len(self.children) == 0
21
22    def is_root(self) -> bool:
23        return self.parent is None
24
25
26def build_demo_tree() -> TreeNode:
27    A = TreeNode("A")
28    B = A.add_child(TreeNode("B"))
29    C = A.add_child(TreeNode("C"))
30    D = A.add_child(TreeNode("D"))
31
32    B.add_child(TreeNode("E"))
33    B.add_child(TreeNode("F"))
34
35    G = C.add_child(TreeNode("G"))
36    G.add_child(TreeNode("K"))
37
38    D.add_child(TreeNode("H"))
39    D.add_child(TreeNode("I"))
40    D.add_child(TreeNode("J"))
41    return A
42
43
44if __name__ == "__main__":
45    root = build_demo_tree()
46    print("root label:", root.label)
47    print("root degree:", len(root.children))
48    print("first leaf under B:", root.children[0].children[0].label)

Computing Height and Depth from a Node

Two of the numbers we defined — depth and height — are computed by tiny recursive walks. They are the "hello world" of tree algorithms, and you should be able to write them without thinking.

On node K in the demo tree:\n  start: cur = G, d = 1\n  step:  cur = C, d = 2\n  step:  cur = A, d = 3\n  step:  cur = None — stop\n  return 3

On node C in the demo tree:\n  height(K) = 0 (leaf)\n  height(G) = 1 + max(0) = 1\n  height(C) = 1 + max(height(G)) = 1 + 1 = 2

If the children's heights are [0, 1, 0], max is 1 and we return 2. The tallest descendant lives via the middle child.

Output:\n  depth(K) = 3\n  height(root) = 3\n  height(C) = 2

1from tree import TreeNode, build_demo_tree
2
3
4def depth(node: TreeNode) -> int:
5    """Edges from the root to this node."""
6    d = 0
7    cur = node.parent
8    while cur is not None:
9        d += 1
10        cur = cur.parent
11    return d
12
13
14def height(node: TreeNode) -> int:
15    """Edges on the longest downward path from node to a leaf."""
16    if not node.children:
17        return 0
18    return 1 + max(height(c) for c in node.children)
19
20
21def height_of_tree(root: TreeNode) -> int:
22    return height(root)
23
24
25if __name__ == "__main__":
26    root = build_demo_tree()
27    K = root.children[1].children[0].children[0]   # A -> C -> G -> K
28    print("depth(K) =", depth(K))                  # 3
29    print("height(root) =", height_of_tree(root))  # 3
30    print("height(C) =", height(root.children[1])) # 2

Pattern. Almost every tree algorithm in this book follows the shape of height: a base case for the empty or leaf subtree, and a recursive case that combines the answers from each child. Internalize this pattern now and the rest of the chapter will feel like variations on a theme.

Edge Cases: Empty Trees, Single Nodes, Forests

Three boundary cases come up constantly in interviews and in real code, and getting them right is what separates a robust tree library from a leaky one.

• The empty tree. The recursive definition allows $T = \emptyset$. In code this means the root pointer can be NULL (in C) or None (in Python). Every recursive algorithm must handle this case explicitly — usually with if node is None: return ... on the first line. The height of the empty tree is conventionally $-1$, so that $\text{height}(\text{leaf}) = 1 + \text{height}(\emptyset) = 0$ comes out right.
• The single-node tree. One node, zero edges. It is simultaneously the root, a leaf, the only ancestor of itself, and the only descendant of itself. depth = 0, height = 0, degree = 0. Test every traversal you write against this case before trusting it.
• The forest. A collection of disjoint trees. Forests arise when you split a tree into parts (e.g. remove the root) or when an algorithm naturally produces several disconnected hierarchies (e.g. Kruskal's minimum-spanning-tree algorithm maintains a forest of growing components, Chapter 21). A forest can be turned into a single tree by adding a fake super-root with the forest's trees as its children — a useful trick when an algorithm requires a single root.

Where Trees Live in the Real World

It is worth pausing at the end of a foundational section to look outward. The terminology you just learned is the same terminology used by the engineers who built the systems you use every day.

Read this table back to yourself with the words you learned in this section. The Git commit DAG is "almost a tree" with merge commits introducing extra parents; B-tree indexes are balanced trees with very high degree (typically hundreds), giving an extremely small height; the DOM is a general tree in which leaves are usually text nodes; an AST is a tree whose internal-node degree depends on the syntactic category. The same vocabulary, applied everywhere.

Quick Check

What Comes Next

You now have the vocabulary (root, parent, child, sibling, leaf, ancestor, descendant, subtree), the numbers (depth, height, level, degree), the mathematical properties ($n - 1$ edges, unique path, height bounds), the C and Python encodings, and the recursive pattern that every tree algorithm follows. Section 10.2 will widen the lens and survey the four standard representations of trees in memory — first-child / next-sibling, array-of-children, parent-pointer-only, and array-indexed (the heap-style flat encoding) — with a clear rubric for which to use when.

Sections 10.3 and 10.4 will then introduce the four classical traversals (preorder, inorder, postorder, level-order), each of which is a one-page recursive program built on the same node structures we defined here. By the end of the chapter you will have written, by hand, every operation you need to implement a basic file viewer, a simple expression evaluator, or a generic tree visitor.