4.2.5.1 - Trees, rooted trees and binary trees (Java)

Trees without cycles

A tree connects its vertices without offering a circular route back to a starting vertex.

Connected means there is a path between every pair of vertices. No cycles means there is no closed path that uses distinct edges without retracing an edge. Together these properties give exactly one simple path between any two vertices. Removing an edge disconnects a tree; adding an edge between two existing nonadjacent vertices creates a cycle.

A tree does not have to have a root. The graph with edges A—B, A—C and C—D is a tree even before one vertex is selected as a starting point. Adding B—D creates a cycle A—B—D—C—A. Two disconnected acyclic groups form a forest rather than one tree. For a finite tree with $n$ vertices there are $n-1$ edges, but the edge count alone does not prove an arbitrary graph is a tree.

Rooted parent-child relationships

Selecting a root makes the direction of ancestry meaningful without changing the underlying tree edges.

The root is the designated starting vertex and the only vertex with no parent. Each other node has one parent: its neighbour on the path toward the root. A node's children are its immediate successors away from the root. Descendants include children and their descendants; ancestors lie on the path back to the root. A leaf has no children, and siblings have the same parent.

[DIAGRAM: asset_slug: rooted_binary_tree; description: Root A has children B and C; B has children D and E; C has children F and G. D, E, F and G are leaves.]

In this diagram, B is the parent of E, A is an ancestor of E, and E is a descendant of A. C is not E's parent. The path from E to F is E—B—A—C—F. Rerooting at B would change which nodes are parents and children, while retaining the same undirected edges.

Rooted trees model file-system folders, organisation hierarchies, decisions and structured expressions. An ordinary folder hierarchy may have many children per folder; it need not be binary. A model which gives a node two different parents is not this rooted-tree structure.