Algorithms Notes – Trees

Example of a tree. 8 is the root. 3 and 10 are children of 8. 1, 13, 4 and 7 are leaves. 10 is an ancestor of 13. 4 is a descendant of 3. 3 is also a descendant of 3 but not a proper descendant. 10 is an ancestor of 10 but not a proper ancestor.

Recursive Definition of a Tree:

Def: A tree is a collection of nodes. If the collection can be empty, in which case it is usually denoted as $\Lambda$. Otherwise, it consists of a node $r$, called the root, and zero or more (sub)-trees $T_{1}, T_{2}, ... , T_{k}$ each of whose roots are connected by a directed edge to the r.

Def: Let $r$ be the root of a tree with one or more subtrees connected to it. The root of any sub-tree connected to $r$ is called a child of $r$.

Def: Let $r_{2}$ be the root of a sub-tree and $r_{1}$ be the root node the subtree is connected to. $r_{1}$ is called the parent of $r_{2}$.

Def: A node in a tree that has no children is referred to as a leaf of the tree.

Def: Let $n_{1}$ and $n_{2}$ be two nodes in a tree that have the same parent. $n_{1}$ is called the sibling of $n_{2}$ and vice versa.

Def: A sequence of nodes $n_{1}, n_{2}, .... , n_{k}$ such that $n_{i}$ is the parent of $n_{i+1}$ for $1 \leq i \leq k$ is referred to as a path.

Def: The number of edges in a path is called the length of the path.

Assertions that have beautiful proofs which you should look up:

• There is a path of length $0$ from every node to itself in a tree.
• In a tree, there is exactly one path from the root to each node.

Def: For any node, $n$ in a tree, the depth of $n_{i}$ is the length of the unique path from the root of the tree to $n$.

• By definition, the depth of the root is $0$.

Def: Let $n$ be any node in a tree. The height of $n$ is the length of of the longest path from $n$ to a leaf.

• By definition, all leaves have a height of $0$.
• The height of a tree is basically the height of the root.

Def: Let $n_{1}$ and $n_{2}$ be two nodes in a tree. If a path exists between $n_{1}$ and $n_{2}$ then $n_{1}$ can be called an ancestor of $n_{2}$. If $n_{1} \neq n_{2}$ then $n_{1}$ is a proper ancestor of $n_{2}$.

Def: Let $n_{1}$ and $n_{2}$ be two nodes in a tree. If a path exists between $n_{1}$ and $n_{2}$ then $n_{2}$ can be called a descendant of $n_{1}$. If $n_{1} \neq n_{2}$ then $n_{2}$ is a proper descendant of $n_{1}$.