Concept of Trees

Some Terminologies:

Tree: A tree is a connected undirected graph. A tree cannot contain multiple edges or loops. Therefore, any tree must be a simple graph. An undirected graph is a tree if and only if there is a unique simple path between any two of its vertices.

Parent: If v is a vertex in Tree other than the root, a vertex u is the parent of v if there is an edge from u to v.

Child/Son: If u is the parent of v, then v is called child/son of vertex u.

Example: From the figure below, G1 and G2 are trees, because both are connected graphs. G3 is not a tree because e, b, a, d, e is a simple circuit in this graph. Finally, G4 is not a tree because it is not connected.

Siblings: Vertices with the same parent are called siblings of each other.

The degree of Vertex (Node): Degree of a vertex is the number of a subtree of that vertex in a given tree.

Ancestors: The ancestors of a vertex other than the root are the vertices in the path from the root to vertex v (excluding the vertex itself).

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 vertex (Non-leaf): A vertex that has at least one child is called internal vertex.

Subtree: If V is a vertex in a tree, the subtree with V as its root is the subgraph of the tree consisting of V and its descendants and all edges incident to these descendants.

Path: A sequence of vertices and edges connecting a vertex with a descendant.

Level: The number of edges in the path from the root to that vertex. The level of the root is zero and level of the descendant is one more than its parent vertex.

The height of Tree: The height of a tree is the number of edges on the longest path from the root to a leaf.

The height of node (Vertex): The height of a node is the number of edges on the longest path from that node to a leaf.

The depth of a Vertex: The length of the unique path from the root to that vertex. The depth of a tree is equal to the depth of its deepest leaf.

Example:

In the given Tree above,

• The parent of c is b.

• The children of g are h, i, and j.

• The siblings of h are i and j.

• The ancestors of e are c, b, and a.

• The descendants of b are c, d, and e.

• The internal vertices are a, b, c, g, h, and j .

• The leaves are d, e, f ,i, k, l, and m.

• The subtree rooted at g is shown in Figure b.

• The level of a is 0, level of d is 3 and level of f is 1.

• The height of the tree is 3, height of h is 2 in figure a & b and height of f is 0.

• The depth of e is 3, depth of k is 3 in figure a and depth of k is 2 in figure b.

References

1. Y. Langsam, M. J. Augenstein and A. M Tenenbaum, “Data Structures using C and C++”

2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, “Introduction toAlgorithms”

3. G. Brassard and P. Bratley, “Fundamentals of Algorithms”