Rooted Tree

A tree with a root vertex.

Height

Length of the longest path from the root.

Level

For a given vertex $v$, length of the simple path from the root to $v$.

Parent

For a given vertex $v$, its parent vertex is the unique vertex $u$ where $\text{level}(u) = \text{level}(v) - 1$ and there is an edge between $u$ and $v$.

Child

For a given vertex $v$, $u$ is a child of $v$ iff $v$ is the parent of $u$.

Siblings

Vertices with the same parent.

Ancestors

For a given vertex $v$, all vertices in the path from the root to $v$, excluding $v$ and including the root.

Descendants

For a given vertex $v$, all vertices that have $v$ as their ancestor.

Leaf

A vertex without any children.

Internal vertices

Vertices that have children. Non-leaf vertices.

Sub-rooted tree

Suppose $a$ is a vertex in a tree. Then the sub-tree with $a$ as its root is the sub-graph of the tree consisting of $a$ and its descendants and all edges incident to these descendants.

Ordered Rooted Tree

Rooted tree with a specified left-to-right ordering among siblings.

Labeling scheme (recursive):

1. Root $\to$ label $0$. Its $k$ children at level 1 $\to$ labels $1, 2, \ldots, k$ (left to right).
2. Vertex at level $n$ with label $A$, having $k_v$ children $\to$ children labeled $A.1, A.2, \ldots, A.k_v$.

Decision tree

Vertices represent the decision points or events, where a decision could be made. Edges represent the possible decisions/outcomes of different choices.