Page 208 - DCAP407_DATA_STRUCTURE

Unit 11: Introduction to Binary Trees

11.1 Types of Binary Trees

Binary trees can be classified on the basis of the level of nodes and the number of nodes that are present
at each level of the tree. The types of binary trees are:
1. Complete binary tree
2. Strictly binary tree
3. Extended binary tree
Complete Binary Tree

A tree is known as a complete binary tree if each of its level, except the last level, is completely filled
and all nodes are as far left as possible. Therefore, at any level ‘l’, the maximum number of nodes must
be equal to 2 . In a complete binary tree, at level 0 there must be only one node known as root node and
l
it should have a maximum of two sub nodes at level 1, and at level 2 there must be a maximum of 4 sub
nodes. Figure 11.3 depicts a complete binary tree. The figure depicts the nodes in the binary tree with
their associated levels.

Figure 11.3: A Complete Binary Tree

In the figure 11.3, the node T1 at level 0 represents the root node. The two sub nodes T2 and T3 are the
child nodes at level 1. The successor nodes T4, T5, T6 and T7 are the terminal nodes. The number of
nodes at level 1 is equal to 2. Similarly, the number of nodes at level 2 is equal to 4.
The main advantage of a complete binary tree is that the position of the parent node and child node can
be mapped easily in an array. The mapping for a binary tree is defined by assigning a number to every
node in the tree. The root node is assigned the number 1.For the other nodes, if i is its number, then the
left child node is assigned the position 2i and the right child node is assigned the position 2i+1. The
mapping of binary tree provides a simple form of array storage representation. Hence the nodes in an
array can be stored as a[i], where a[ ] is an array.

LOVELY PROFESSIONAL UNIVERSITY 201