Data Structure – Binary Tree Concepts

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.

Learn Tree Basics

Informal definition

A tree is called a binary tree if it has the following properties.

  1. It is an empty tree with no nodes.
  2. The tree has a root node, left sub-tree and right sub-tree.
  3. 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.

Strictly Binary Tree - Binary Tree Concepts
Strictly Binary Tree – Binary Tree Concepts

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,

Complete Binary Tree - Binary Tree Concepts
Complete Binary Tree – Binary Tree Concepts

The root is at level 0, therefore, L = 0 and 2^L = 2^0 = 1.

Conversion of a Binary forest into a Binary Tree

Suppose we have a forest with two trees as follows,
Forest with Two Trees - binary tree concepts
Forest with Two Trees
T1 = { 1,2,3,4,5,6}
T2 = { 7,8,9,10,11,12}
The figure below show the two separate trees  in the forest.
The first step is to order the nodes of both trees using following formula.
  • 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.
Such a representation of two trees is given below.
Forest with Two Ordered Trees - binary tree concepts
Forest with Two Ordered Trees
Your next step should be to join these two tree into one by connecting their roots. This is because the roots of the trees are at the same level. See the figure below
Forest with Two Ordered Trees Joined - Binary tree concepts
Forest with Two Ordered Trees Joined
The new tree is a binary tree, the node at the save level in above diagram becomes the right child. The final tree structure look like the one in figure below.
Final Joined Binary Tree - Binary Tree Concepts
Final Joined Binary Tree

 

Total Number of Edges

In a complete binary tree, the total number of edges is given by the formula,

2 ( NL – 1) where Nis total number of leaf nodes. For example, see the tree below.

Complete Binary Tree with Edge Labelled -Binary Tree Concepts
Complete Binary Tree with Edge Labelled

In the above diagram, we have NL = 8 .
Therefore,

 

= 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.

Height Of The Tree - Binary Tree Concepts
Height Of The Tree

 

In the above tree figure, the maximum level of the tree is 4,
Therefore, the height of the tree is Height(T) = 4.

 


Bibliography

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.

 

Advertisements