Graphs / Rooted Trees
Least You Need to Know: Rooted Trees
A rooted tree picks one vertex as the root, which gives every other vertex a parent-child relationship and a level.
The least you need to know
- The root has no parent.
- Every non-root vertex has exactly one parent.
- Leaves are vertices with no children.
- Subtrees inherit the tree structure below a chosen vertex.
Key notation
root
distinguished top vertex
parent(v)
the vertex directly above v
depth
distance from the root
Tiny worked example
- In a rooted tree with root r and edges `r-a, r-b, a-c`, the parent of c is a.
- The leaves are b and c.
- The depth of c is 2 because it is two edges from r.
Common mistakes
- Students often think the root is the only vertex allowed to have children.
- Students often call any degree-1 vertex a leaf even when it is the root in a one-vertex tree.
- Students often confuse parent with ancestor.
How to recognize this kind of problem
- Every child is one edge farther from the root than its parent.
- Leaves are about children, not total degree in the underlying unrooted tree.
- A subtree includes a vertex and all of its descendants.