Rooted Trees

A directed tree is a directed graph for which the underlying undirected graph is a tree.

A directed tree is called a rooted tree if there is a unique vertex $r$, called the root so that $r$ has in-degree 0, and all other vertices have in-degree 1.

A leaf in a rooted tree is a vertex with outdegree zero.

A branch node is a vertex which is not a leaf.

Level $k$ of a rooted tree is the level containing all vertices at distance $k$ from the root.

If there is an edge $(u,v)$ in a rooted tree, then $v$ is a child of $u$, and $u$ is the parent of $v$.

An ancestor of a vertex $v$ is a vertex on the path from $r$ to $v$. Vertex $v$ is a descendant of $u$ if $u$ is an ancestor of $v$.

Two vertices with a common parent are called siblings.

The subtree at vertex $v$ is the subgraph induced by the root $v$ and all of its descendants.

A binary rooted tree is such that every vertex has at most two children. It is a complete binary tree if every branch node has exactly two children.