Trees

Overview

A free tree is a connected, acyclic, undirected graph. If an undirected graph is acyclic but possibly disconnected, it is a forest.

Rooted Trees

A rooted tree is a free tree in which one vertex is distinguished/blessed as the root. We call vertices of rooted trees nodes.

Let $T$ be a rooted tree with root $r$. Any node $y$ on the path from $r$ to node $x$ is an ancestor of $x$. Likewise, $x$ is a descendant of $y$. If the last edge on the path from $r$ to $x$ is $\{y,x\}$, $y$ is the parent of $x$ and $x$ is a child of $y$. Nodes with the same parent are called siblings.

A node with no children is an external node or leaf. A node with at least one child is an internal node or nonleaf. The number of children of a node is the degree of said node. The length of the path from the root to a node $x$ is the depth of $x$ in $T$. A level of a tree consists of all nodes at the same depth. The height of a node in a tree is the length of the longest path from the node to a leaf.

Ordered Trees

An ordered tree is a rooted tree in which the children of each node are ordered.

Positional Trees

A positional tree is a rooted tree in which each child is labeled with a specific positive integer. A $k$-ary tree is a positional tree with at most $k$ children/labels. A binary tree is a $2$-ary tree.

A $k$-ary tree is full if every node has degree $0$ or $k$. A $k$-ary tree is perfect if all leaves have the same depth and all internal nodes have degree $k$. A $k$-ary tree is complete if the last level is not filled but all leaves have the same depth and are leftmost arranged.

Bibliography

• Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022).