Course contentsShow
← Mathematics
Lesson 2670 of 3,12153. Graph TheoryFree lesson

Rooted Trees and Terminology

Understand rooted trees, including parents, children, ancestors, descendants, and leaves.

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:

  • u is the parent of v
  • v is a child of u
  • Vertices with the same parent are siblings

Ancestors and Descendants

  • An ancestor of vertex v is any vertex on the unique path from the root to v (including the root, excluding v itself)
  • A descendant of vertex v is any vertex in the subtree "below" v (reachable by traveling away from the root through v)

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.