# 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. Share