STEP-BY-STEP LESSON · §10.5
Rooted Trees
Read parents, descendants, and depth in a rooted tree.
Before you begin
Trees
A tree is a nonempty undirected graph that is connected and has no cycle. It has exactly one simple path between any two vertices, so deleting any edge disconnects it. A finite tree with n vertices has n−1 edges.
The unique path in a tree
Connectedness supplies a path; two different simple paths between the same endpoints would produce a cycle. Thus a tree has exactly one. Choosing a root lets that path identify each nonroot vertex’s parent.
Symbols
- depth(v)
- number of edges from the root to v
Definitions and notation for this topic
Root and depth
depth(v)
A rooted tree has a designated root. The depth of v is the number of edges on the unique path from the root to v; the root has depth zero.
The parent is the preceding vertex on that root path; children are one level farther away. Depth counts edges, not vertices, and is not a vertex’s degree.
Separate glossary example
If r is the root and the path is r—a—v, then depth(a)=1 and depth(v)=2.
Step by step
Step 1 / 6
Choose a root
The root gives an outward direction. Every other vertex has a parent: its neighbor on the unique path toward the root.
Without a root, the same edge has no fixed parent-child roles.
Worked example
Root R has children A,B; A has child C. Find depths and height.
- depth(R)=0; depth(A)=depth(B)=1.
- R→A→C has two edges: depth(C)=2. The height is 2.
- It is binary but not full: A has only one child.
Optional self-check
Can a finite full binary tree have ten vertices? Use an edge count rather than a drawing.
Show answer
No. With i internal vertices it has 2i child edges and therefore 2i+1 total vertices, an odd number.