Rooted Trees and Terminology
What you'll learn: How designating one vertex as the "root" creates a hierarchical structure with parent-child relationships in a tree.
What Is a Rooted Tree?
A rooted tree is a tree where we've designated one special vertex as the root. This choice imposes a natural hierarchy: all edges are considered to point "away from" the root, creating parent-child relationships throughout the tree.
Think of it like a family tree or a corporate organization chart—there's one person at the top (the root), and everyone else has a clear position relative to that starting point.
Key Terminology
Parent, Child, and Siblings
When vertex u is directly connected to vertex v and u is closer to the root, we say:
uis the parent ofvvis a child ofu- Vertices with the same parent are siblings
Ancestors and Descendants
- An ancestor of vertex
vis any vertex on the unique path from the root tov(including the root, excludingvitself) - A descendant of vertex
vis any vertex in the subtree "below"v(reachable by traveling away from the root throughv)
Leaves and Internal Vertices
- A leaf (or external vertex) is a vertex with no children—it's a "dead end" in the hierarchy
- An internal vertex is any non-leaf vertex (it has at least one child)
- The root is internal unless the tree has only one vertex
Levels and Height
- The level of a vertex is its distance from the root (root is at level 0)
- The height of the tree is the maximum level of any vertex
Key Takeaway: Rooting a tree creates a top-down hierarchy where every vertex (except the root) has exactly one parent, enabling us to describe relationships like ancestors, descendants, and leaves based on position relative to the root.