Page 103 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes 5.1 Concept of Tree

A tree is a set of one or more nodes T such that:
1. There is a specially designated node called root, and
2. Remaining nodes are partitioned into n >= 0 disjoint set of nodes T , T ,…,T each of which
2
n
1
is a tree.
Shown below in Figure 5.1 is a structure, which is tree.
Figure 5.1: A Tree Structure

A

B C D

G H I E F

This is a tree because it is a set of nodes {A, B, C, D, E, F, G, H, I}, with node A as a root node,
and the remaining nodes are partitioned into three disjoint sets: {B, G, H, I}, {C, E, F} AND {D}

respectively. Each of these sets is a tree individually because each of these sets satisfies the above
properties. Shown below in Figure 5.2 is a structure, which is not a tree:
Figure 5.2: A Non-tree Structure

A

B C D

G H I E F

This is not a tree because it is a set of nodes {A, B, C, D, E, F, G, H, I}, with node A as a root node,
but the remaining nodes cannot be partitioned into disjoint sets, because the node I is shared.
Given below are some of the important definitions, which are used in connection with trees.

1. Degree of Node of a Tree: The degree of a node of a tree is the number of sub-trees having
this node as a root, or it is a number of decedents of a node. If degree is zero then it is called
terminal node or leaf node of a tree.

2. Degree of a Tree: It is defined as the maximum of degree of the nodes of the tree, i.e. degree

of tree = max (degree (node i) for i = 1 to n).

3. Level of a Node: We define the level of the node by taking the level of the root node to be 1,
and incrementing it by 1 as we move from the root towards the sub-trees i.e. the level of all
the descendents of the root nodes will be 2. The level of their descendents will be 3 and so

on. We then define depth of the tree to be the maximum value of level for node of a tree.

98 LOVELY PROFESSIONAL UNIVERSITY