Rooted Trees

A rooted tree is a tree with a special vertex labelled as the "root" the of tree.

The root serves as a point of reference for other vertices in the tree. In diagrams, we usually keep the root at the top and list other vertices below it.

This notion is particularly useful in computer science for working with tree-based data structures.

In the figure, the root vertex is shown with a black border.

Below are some useful terms associated with rooted trees.

Branch is just another name given to edges of the tree.

Depth of a vertex is the number of branches in the path from root to the vertex. So depth of the root itself is zero.

Level of a vertex is number of vertex in the path from root to the vertex. This is just one more than the depth of the vertex. Level of root is 1.

Child of a vertex v1v1 is any vertex v2v2 connected to it such that d(v2)=d(v1)+1d(v2)=d(v1)+1, where d(v)d(v) denotes depth of vertex vv. v1v1 is called parent of v2v2. Usually, in diagrams, we keep the parent vertex above its child vertices.

Note: There can be multiple childs of a vertex, but parent of a vertex is unique. Root is the only vertex in a tree without any parent.

A leaf is a vertex without any child.

Height of tree is the maximum value of depth for any vertex in the tree.

Play around to get yourself familiar with these terms. By the way, did you notice something about the colors?

Theorem: All tree graphs are bipartite.

This can be easily seen by coloring all the vertices at even depth in a color, say pink, and coloring the vertices at odd depth in another color, say cyan. So, any tree is 2-colorable.