Binary Trees

A binary tree is a special case of tree as defined in the preceding section, in which no node of a tree can have a degree of more than 2. Therefore, a binary tree is a set of zero or more nodes T such that:
 
(i) there is a specially designated node called the root of the tree

(ii) the remaining nodes are partitioned into two disjointed sets, T1 and T2, each of which is a binary tree. T1 is called the left subtree and T2 is called right subtree, or vice-versa.

A binary tree is shown in following Figure.

So, for a binary tree we find that:
 
(i) The maximum number of nodes at level i will be 2i−1
 
(ii) If k is the depth of the tree then the maximum number of nodes that the tree can have is
 
2k − 1 = 2k−1 + 2k−2 + … + 20
 
Also, there are skewed binary trees, such as the one shown in following Figure.

A full binary tree is a binary of depth k having 2k − 1 nodes. If it has < 2k − 1, it is not a full binary tree. For example, for k = 3, the number of nodes = 2k − 1 = 23 − 1 = 8 − 1 = 7. A full binary tree with depth k = 3 is shown in following Figure.

We use numbers from 1 to 2k − 1 as labels of the nodes of the tree.
 
If a binary tree is full, then we can number its nodes sequentially from 1 to 2k−1, starting from the root node, and at every level numbering the nodes from left to right.
 
A complete binary tree of depth k is a tree with n nodes in which these n nodes can be numbered sequentially from 1 to n, as if it would have been the first n nodes in a full binary tree of depth k.
 
A complete binary tree with depth k = 3 is shown in following Figure.

Representation of a Binary Tree

If a binary tree is a complete binary tree, it can be represented using an array capable of holding n elements where n is the number of nodes in a complete binary tree. If the tree is an array of n elements, we can store the data values of the ith node of a complete binary tree with n nodes at an index i in an array tree. That means we can map node i to the ith index in the array, and the parent of node i will get mapped at an index i/2, whereas the left child of node i gets mapped at an index 2i and the right child gets mapped at an index 2i + 1. For example, a complete binary tree with depth k = 3, having the number of nodes n = 5, can be represented using an array of 5 as shown in following Figure.

Shown in following Figure is another example of an array representation of a complete binary tree with depth k = 3, with the number of nodes n = 4.

In general, any binary tree can be represented using an array. We see that an array representation of a complete binary tree does not lead to the waste of any storage. But if you want to represent a binary tree that is not a complete binary tree using an array representation, then it leads to the waste of storage as shown in following Figure

An array representation of a binary tree is not suitable for frequent insertions and deletions, even though no storage is wasted if the binary tree is a complete binary tree. It makes insertion and deletion in a tree costly. Therefore, instead of using an array representation, we can use a linked representation, in which every node is represented as a structure with three fields: one for holding data, one for linking it with the left subtree, and the third for linking it with right subtree as shown here:

We can create such a structure using the following C declaration:
 

struct tnode
{
   int data
   struct tnode *lchild,*rchild;
};

A tree representation that uses this node structure is shown in following Figure.