Rooted Trees

Graph Theory · Axiom Academy

Understanding hierarchical structure in trees through the root vertex 1. Designating a Root and Parent-Child Relationships When we select a vertex as the root , it establishes a hierarchy where each edge connects a parent vertex to its child vertices. The parent is always closer to the root. 2. Ancestors, Descendants, and Siblings Ancestors are all vertices on the path from a vertex to the root. Descendants are all vertices reachable by moving away from the root. Siblings share the same parent. Ancestor: Any vertex on the path from a vertex to the root (including the root) Descendant: Any vertex in the subtree rooted at a given vertex Siblings: Vertices that share the same parent The depth (or level) of a vertex is the number of edges from the root to that vertex. The height of a tree is the maximum depth of any vertex. 4. Leaf Nodes, Internal Nodes, and Levels Leaf nodes (or leaves) have no children. Internal nodes have at least one child. The level of a node is its depth (distance from root). Leaf (External Node): A vertex with no children (degree 1 in the tree, except if it's the root) Internal Node: A vertex with at least one child (includes the root if it has children) Level: The set of all vertices at the same depth from the root

This is the written version of the interactive lesson above. See the full Graph Theory course.