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.
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
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 it
- 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.
Next recommended lesson
Continue through this topic with Least You Need to Know: Trees.
Least You Need to Know: TreesRelated lessons
Keep going with nearby lessons in the same topic.