Introduction
A rooted tree is a tree in which a special ("labeled") node is singled out. This node is called the
"root" or (less commonly) "eve" of the tree. Rooted trees are equivalent to oriented trees (Knuth
1997, pp. 385-399). A tree which is not rooted is sometimes called a free tree, although the
unqualified term "tree" generally refers to a free tree.
A rooted tree in which the root vertex has vertex degree 1 is known as a planted tree.
A rooted tree GG is a connected acyclic graph with a special node that is called the root of the tree
and every edge directly or indirectly originates from the root. An ordered rooted tree is a rooted
tree where the children of each internal vertex are ordered. If every internal vertex of a rooted tree
has not more than m children, it is called an m-ary tree. If every internal vertex of a rooted tree has
exactly m children, it is called a full m-ary tree. If m=2m=2, the rooted tree is called a binary tree.
Parent
Suppose that T is a rooted tree. If v is a vertex in T other than the root, the parent of v is the
unique vertex u such that there is a directed edge from u to v.
Child
If u is the parent of v, then v is called a child of u.
Siblings
Vertices with the same parent are called siblings.
Ancestors
The ancestors of a vertex other than the root are the vertices in the path from the root to this
vertex, excluding the vertex itself and including the root.
Descendants
The descendants of a vertex v are those vertices that have v as an ancestor.
Leaf
A vertex of a tree is called a leaf if it has no children.
Internal Vertices
Vertices that have children are called internal vertices.
Subtree
If a is a vertex in a tree, the subtree with a as its root is the subgraph of the tree consisting of a
and its descendants and all edges incident to these descendants.
Some Important Terms for Rooted Trees:
1. If the starting path is (a, b) in a rooted tree, a is called the parent of b.
2. If a has children, then a is internal node
3. If a has no children, then b is a leaf.
4. a and b are siblings if they have same parent.
5. The height of a tree is measured as the length of the longest possible path from its root to
any vertex.
6. The level of a vertex is known as the path length from its starting point or the root. The root
is starts from the point 0.
7. Here, a the starting point is known as an ancestor of b.
8. Here, b is known as a descendent of a. Note that here, a is an ancestor.n-ary Trees:
A rooted tree is called as n-ary tree if every vertex has no more than n children. It is called as full
if each internal vertex that is non leaf has exactly n children. A binary tree is any example of a 2
ary tree. These are very useful for taking decisions of yes or no problems.
In other words, a rooted tree is an n-ary tree if and only if every internal vertex has less than
equal to n children. If every internal vertex are found to having exactly m children then it is
considered as a full n-ary tree.
Problem Statement
i) What is the function of rooted tree in our daily life ?
ii) How rooted tree was established ?
iii) How to uses rooted tree ?
iv) What is characteristics of rooted tree ?
v) What is the edges of rooted tree ?
vi) What is the decomposition of rooted tree ?
vii) What is the different between rooted tree and unrooted tree ?
viii) What is the main objective using rooted tree ?