Page 188 - DCAP407_DATA_STRUCTURE

Unit 10: Trees

Path
Every node in the tree is reachable from the root node through a unique sequence of links. This
sequence of links is known as a path. The number of links in a path is considered to be the length of the
path.
In figure 10.2, the length of the path from A to D = (the link from A to B) + (the link from B to D)
= 1 + 1
= 2

Levels
The level of a node in the tree is considered to be its hierarchical rank in the tree. In figure 10.4, the root
node A, is at level 0.
Consider a node which is at level L. Then,
The level of its parent node = L-1

The level of its child node = L+1
This rule does not apply to a root node as it does not have a parent node. In figure 10.4, node A is at
level 0, nodes B and C are at level 1. Nodes D, E, F, and G are at level 2 and node H is at level 3.
Number of nodes in the path = (the length of the path from the root to the node) +1
In figure 10.4, the number of nodes in the path from A to D

= (the length of the path from the root to the node) + 1
= {(the link from A to B) + (the link from B to D)} + 1
= {(1) + (1)} + 1
= {2} + 1
= 3
Height

The height of a non-empty tree is the maximum level of a node in the tree. The height of an empty tree
(no node in a tree) is 0. The height of a tree containing a single node is 1. The longest path in the tree has
to be considered to measure the height of the tree.

Height of a tree (h) = I max+ 1, where I max is the maximum level of a tree.
In figure 10.4, the maximum level of the tree is 3.
So, height of the tree (h) = I max+ 1
= 3 + 1
= 4
Degree (Arity)

The degree or arity of a node is the maximum number of children that a node has. In figure 10.4, the
degree of node A is 2; the degree of node B is 1; and the degree of node C is 3.
Siblings
The nodes which have the same parent node are known as siblings. In figure 10.4, nodes B and C are
siblings as they have have the same parent node, A.
Graphs consist of a set of nodes and edges, just like trees. But for graphs, there are no rules for the
connections between nodes. In graphs, there is no concept of a root node, nor a concept of parents and
children. Rather, a graph is just a collection of interconnected nodes. All trees are graphs. A tree is a
special case of a graph, in which the nodes are all reachable from some starting node.

LOVELY PROFESSIONAL UNIVERSITY 181