Introduction to Binary Tree

Binary Trees are defined as a tree data structure where each parent node has at most two children or no child node or we can simply say that it's a tree data structure which has a maximum of degree two or the child node has no sibling. One simple example of a Binary tree is shown below:

A binary tree can be empty or it can consist of a root node and two disjoint binary trees the left subtree and the right subtree. Also, binary trees are different from the simple trees as a binary tree (binary means two) can have at most two children but a simple tree can have more than two children due to which in a binary tree every node is sequentially numbered.

Important Properties Of Binary Trees

Following are some of the important properties of a binary tree:

1. The maximum number of nodes at any level i of a binary tree with the level of the root node being zero is equal to 2i and 2i-1 when the level of the root node is considered as one. For example, in the diagram given above, the level of the root is considered to be zero hence, in the first level there are a total number of two nodes with data 2 and 3 and in the next level there are a total of four nodes with data 4, 5, 6, and 7 as per the given relation.

2. The parent nodes in a binary tree and the terminal nodes or the leaf nodes in a binary tree have a relation m = n - 1 (where m is the total number of the inner nodes or the parent nodes in a binary tree and n is the total number of the terminal nodes or leaf nodes in a binary tree). For example, in the diagram of the binary tree above, the total number of leaf nodes or the terminal nodes are four and the total number of inner nodes or the parent nodes in the given binary tree are three which is one less than the total number of leaf nodes or the terminal nodes as per the given relation.

3. The total number of maximum nodes in a binary tree with height h is 2h - 1. For example, in the diagram of a binary tree above, where the height of the tree is three, the total number of maximum nodes is seven as per the given relation.

4. The maximum number of the parent nodes in a binary tree on any given level i will be 2i (level of the root being zero) and log2 2i (level of the root being one). For example, in the diagram above, the total number of parent nodes on the level zero is one with data 1 and on the level one is two with data 2 and 3 considering the level of the root is taken to be zero else, in this case, the result will still be the same but the relation will change.

5. If a binary tree has a total of n nodes then the minimum possible number of height and the level of a binary tree will be the ceiling value of log2(n + 1). For example, in the above binary tree with a total of seven nodes, the value of level and height are both three (taking the level of the root as one).

6. The minimum level of a binary tree with l leaf nodes will be the ceiling value of log2l + 1 (if the level of the root is taken to be one) else log2l (if the level of the root is taken to be zero). For example, in the diagram of a binary tree above, the total number of leaf nodes or the terminal nodes is four and the level of the binary tree is three for the level of root taken as one and two for the level of root taken as zero.

Types Of Binary Tree

Some of the different types of binary trees are as follows:

1. Full Binary Tree

2. Complete Binary Tree

3. Perfect Binary Tree

4. Infinite Complete Binary Tree

5. Balanced Binary Tree

Let's learn more about these different types of binary tree.

1. Full Binary Tree

A full binary tree is the type of binary tree where there are a total of 2h - 1 nodes (where h is the height of a binary tree) or a full binary tree can also be defined as the binary tree in which every parent node has a total of two child node or no child node, but not a single child node.

It is also known as the strictly binary tree, plane binary tree or a proper binary tree.

Following are some of the important properties of a full binary tree:

• If a binary tree has n internal nodes then the total number of leaf node m will be m = n + 1. For example, in the diagram for a binary tree above, there are a total of three internal nodes with data 1, 2, and 5 and according to the above binary tree relations, a total of four leaf nodes are there with data 3, 4, 10, and 11.

• If a binary tree has n internal nodes then the total number of nodes m in the tree will be m = (2 * n) + 1. For example, in the diagram above there are a total of three internal nodes with data 1, 2, and 5 and according to the given relation, a total of seven nodes with data 1, 2, 3, 4, 5, 10 and 11 are there.

• If a binary tree has a total of n nodes then the total number of leaf nodes l will be l = (n + 1) / 2. For example, in the above diagram there are a total of seven nodes with data 1, 2, 3, 4, 5, 10 and 11 and according to the given relation, a total of four leaf nodes with data 3, 4, 10 and 11.

2. Complete Binary Tree

A complete binary tree is defined as a binary tree with all of its node numbered sequentially as shown in the diagram below where the serial number of the nodes is equal to their data stored at each node. A complete binary tree is also a binary tree in which its nodes should be as left as possible(in other words first the left side is filled) and all the levels of a binary tree should be completely filled except the last level.

Following are some of the important properties of a complete binary tree:

• A complete binary tree of height h has a maximum of 2^(h+l) - 1 nodes. For example, in the above diagram the height of the tree is four and according to the given relation there could be a total of a thirty-one node but here it has a total of eight nodes.

• The height of a complete binary tree is log2(n) where n is the number of nodes in a complete binary tree. For example, in the diagram above the total number of nodes in the given binary tree is 8 and according to the given relation, the height of the tree will be 4.

• All the left subtree of a binary tree must be full. As shown in the diagram above the left subtree is completely filled.

• The total number of internal nodes in a complete binary tree is n/2 (where n is the total number of nodes in a complete binary tree). For example, in the diagram above, there are a total of 8 nodes and according to the given relation, there are 4 internal nodes with data 1, 2, 3, and 4.

• The maximum number of NULL link in a binary tree with n nodes is always equal to n + 1. For example, in the above diagram of a binary tree, there are a total of 8 nodes with a maximum of 9 NULL links.

3. Perfect Binary Tree

A perfect binary tree is defined as a binary tree, where all its leaf nodes are at the same level. It is ambiguously also known as a complete binary tree and its properties are same as that of a full binary tree. Below we have an example of a perfect binary tree.

4. Infinite Complete Binary Tree

An infinite complete binary tree is defined as a binary tree in which all parent nodes have two children and the node is countably infinite and the infinite path from the root is uncountable.

5. Balanced Binary Tree

A balanced binary tree is defined as a binary tree with minimum possible maximum heights of all leaf nodes for any number of the leaf nodes present they are in the maximum possible heights. For example, in the diagram below we have a balanced binary tree with a difference in the level of the left subtree as compared to the right subtree of a node.

Representation Of Binary Trees

Binary trees can be represented by using an array or using a linked list data structure.

1. Array Representation of Binary Trees:

Below is the array representation of a binary tree with its data as alphabetical letters, the root node of the tree is with data x followed by its child node with data y which in turn has two child nodes with data z and u.

z node does not have any child node. u node has two child nodes with data v and w.

Now for its array representation we can clearly see that the array position with index as 1 is occupied by the node with data x as the node with data x has only one child node hence, the array position with index as 2 is occupied by the left child node of x since there is no right child node of x hence the array position with index as 3 is empty because we already know that all nodes in a binary tree are sequentially numbered and so should be its array representation.

Similarly the node with data y has both its left and the right child nodes hence the array position with index as 4 and 5 are occupied by the nodes with data z and u and since there is no right child of node with data x, hence it has no child node and array position with index as 6 and 7 will be empty because we already know that all nodes in a binary tree are sequentially numbered.

Also there is no child node for the node with data z and so, the array position with index 8 and 9 will be empty as well and at the end the node with data u, both its left and the right child are present hence, the array position with index 10 and 11 is occupied by the nodes with data v and w.

Always note that while representing a binary tree with an array the left subtree comes before the right subtree.

2. Linked List Representation of Binary Trees:

Below is the linked list representation of a binary tree with a given binary tree having data as alphabetical letters where the root node of the tree is with data x followed by its child nodes just like above.

Now for the linked list representation we can clearly see the nodes with three fields one as a data field and the remaining as the left link field and the right link field and we can also see that some of the nodes have either the left link field as black colored or the right link field as black colored or both of them black colored (this is done to represent the NULL nodes of left and right subtree respectively).

The root node with data x has its left child node with data y and a NULL right child. Then the node with data y has its both left and the right child with data z and u. Similarly, the node with data u has both its left and the right child node with data v and w respectively as shown in the diagram above.

Important Points regarding Linked List Representation of a Binary Tree

Following are some useful points to remember:

• The total number of pointers used to represent a binary tree with n nodes is equal to 2*n.

• The total number of NULL pointers used to represent a binary tree with n nodes is equal to n+1.

Conclusion

Binary trees are a very important data structure used extensively in programming. You might not use all of its different types oftenly but it is always good to have the knowledge.

You may also like:

• Introduction To Binary Trees

• Insertion(Adding a new Node) in a Binary Tree Data Structure

• Trie Data Structure

• What is Hashing?