4.2.5.1 - Trees, rooted trees and binary trees (C#)

Trees without cycles

A tree is a special graph whose connections give exactly one simple path between any two nodes.

Connected means every node is reachable from every other by following edges. A cycle would allow a route to return to its starting node without retracing an edge. A connected cycle-free graph with $n$ nodes has $n-1$ edges. This count is a useful check, but count alone is insufficient: a disconnected graph can have the same total while one component contains a cycle.

For nodes M, F, T, B, H and R, use undirected edges M–F, M–T, F–B, F–H and T–R. All six nodes connect and none of the five edges completes a cycle, so it is a tree. Adding H–T makes a cycle H–F–M–T–H. Removing M–T disconnects T and R from the other nodes. A disconnected collection of trees is a forest, not one tree.

Rooted parent-child relationships

Choosing a root turns undirected tree connections into a hierarchy of parent-child relationships.

Designate M as root of the example. M has children F and T; F has children B and H; T has child R. The root has no parent. Every other node has exactly one parent and is a descendant of the root. An ancestor lies above a node on its route to the root; a descendant lies below. B and H are siblings because they share parent F. B, H and R are leaves because they have no children.

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

Define depth as the number of edges from root to node: M has depth 0; F and T depth 1; B, H and R depth 2. Height is the greatest depth here, 2. Some sources count levels differently, so state the convention when giving numbers.

Folder directories, organisation charts and a decision hierarchy use rooted trees. A folder can have many children, so its tree need not be binary. Real shortcuts/links can create additional relationships; the simple hierarchy model assumes a unique parent for each non-root node. A rooted tree may be stored with a list of children per node or with a parent index for each non-root node.