A binary tree is a special kind of tree and important in computer science. There are plenty of real world application of binary trees. The scope of this lesson is limited to the learning the binary tree concepts.
A tree is called a binary tree if it has the following properties.
- It is an empty tree with no nodes.
- The tree has a root node, left sub-tree and right sub-tree.
- The sub-trees are binary tree themselves.
Strictly Binary Tree
Suppose there is a binary tree with right sub-tree and left sub-tree. The sub-trees are in turn non-empty, then such a binary tree is called a strictly binary tree.
In the above figure, one is a strictly binary tree and the second tree is not a strictly binary tree, but it is certainly a binary tree and satisfy all the properties of a binary tree.
Complete Binary Tree
A complete binary tree has a level L and all its leaf nodes are available at level L. At each level the complete binary tree contains 2Lnodes.
Let us show this with an example,
The root is at level 0, therefore, L = 0 and 2^L = 2^0 = 1.
Conversion of a Binary forest into a Binary Tree
- If a node has left child, then if comes immediately below the node.
- If a node has another node in the save level, then it becomes the right child of the node.
- If a node has right child then, ignore it.
Total Number of Edges
2 ( NL – 1) where NL is total number of leaf nodes. For example, see the tree below.
In the above diagram, we have NL = 8 .
= 2( NL – 1)
= 2 ( 8 – 1)
= 2 (7)
= 14 edges.
Height of a Binary Tree
The maximum level of any node of the binary tree is called the height of a binary tree.
For example, see the figure below.
In the above tree figure, the maximum level of the tree is 4,
Therefore, the height of the tree is Height(T) = 4.
R.G.Dromey. 2008. How to Solve it by Computer. Pearson Education India.
Robert Kruse, Cl Tondo. n.d. Data Structures and Program Design in C. Pearson Education India.
Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein. 2009. Introduction to Algorithms. MIT Press.