tree (graph)

Tree

A tree is a connected, acyclic graph. This means that there is exactly one path between any pair of vertices, and there are no cycles (i.e., no closed loops).

Trees are a generalization of lists: Each node may have multiple successors.

EXAMPLE

Rooted trees have a root, “free trees” have no root.

Terminology

Exactly one node has no predecessor (the root; often by definition).
Nodes without successors are called leaves (or external nodes)
Nodes with successors are called internal nodes.
A tree $B$ is ordered, if sucessors of each node are ordered. (e.g. smaller to the left, larger to the right)
In an ordered tree, the subtrees $B_i$ of each node form an ordered set. (e.g. left subtree < root < right subtree)
The order of $B$ is the maximum number of sucessors of a node.
The distance between two vertices in a tree is the number of edges on the path between them.
The height of a tree is the maximum distance from the root to any leaf.
The depth of a node is its distance to the root (the nodes at level $i$ are all nodes with depth $i$).
A tree is of order $n$ is called complete if all leaves have the same depth, and the maximum number of nodes is present at each level.

---

https://mathworld.wolfram.com/Tree.html