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

Trees without cycles

A tree is a connected, undirected graph containing no cycles; it does not inherently need a root.

Connected means every vertex can be reached from every other by following edges. A cycle would return to its starting vertex along a sequence of distinct edges without simply retracing an edge. A tree has exactly one simple path between any two vertices. If a connection is removed, it splits the tree; adding a new edge between existing vertices creates a cycle. A tree with n vertices has n − 1 edges, but an edge count alone does not establish that a graph is connected and acyclic.

For example, undirected edges A–B, B–C and B–D connect four vertices without a cycle. Designating A or B as a root does not change those underlying edges. Two disconnected chains form a forest, not one tree. Transport networks often have alternative routes and cycles; a hierarchy whose members each have one parent is better represented by a rooted tree.

Rooted parent-child relationships

Choosing one vertex as the root turns the tree's unique paths into parent-child relationships.

The root is the only node with no parent. Every other node has exactly one parent: the adjacent node one step nearer the root. A parent's children lie one step farther from it. A descendant can be reached by following one or more child links; all non-root nodes are descendants of the root. Siblings share a parent. A leaf has no children. The root can itself be a leaf in a one-node tree.

[DIAGRAM: asset_slug: rooted_binary_tree; description: Six-node rooted binary tree with root M, children F and T, F's children B and H, and T's child R]

Here F is H's parent; B and H are siblings; B, H and R are leaves. H is a descendant of M even though it is not M's immediate child. The drawn edges are undirected connections; the chosen root defines how they are interpreted. Rooted trees model folder hierarchies, organisation structures and decision processes. A general folder tree can have many children per folder, so it is not necessarily binary.

One representation maps a node label to its list of children. Another stores a parent index and child references in node records. For a valid rooted tree, adding a fresh node beneath one parent preserves the structure; linking an existing ancestor beneath its descendant would introduce a cycle. A reference connects nodes without copying the whole subtree.

Binary trees and uses

A binary tree is a rooted tree in which each node has at most two children, commonly named left and right.

It may have zero, one or two children. A missing left child does not require a missing right child. In Python, store None for an absent reference: