BINARY TREES

Examples :

Different types of Binary Tree

1. Perfect Binary Tree
   
   A 'Perfect Binary Tree' is a 'Binary Tree' where all the internal Nodes has exactly two Children.
   
   
   
   
   
   The above tree is a 'Perfect Binary Tree' as all the internal Nodes 'A', 'B' and 'C' has exactly two children.
2. Complete Binary Tree
   
   A 'Complete Binary Tree' is a 'Binary Tree' where all the Levels except the last Level should be completely filled.
   
   So, what about the last Level?
   
   The last Level can be partially filled and they must be filled from the Left side.
   
   Let us understand with the below tree.
   
   
   
   
   
   There are three levels in the above Tree. Level 1 and Level 2 are completely filled as Level 1 can have at-most 1 Node and Level 2 can have at most 2 Nodes.
   
   But Level 3 can have 4 Nodes. And Level 3 has 3 Nodes.
   
   But that's fine as Level 3 is the last Level and can have less than 4 Nodes.
   
   And the important thing to note is, all the Nodes are filled from left.
   
   i.e. If we consider the below tree.
   
   
   
   
   
   The above tree is not a 'Complete Binary Tree' as 'F' Node of the last Level(i.e. Level 3) is the right child of Node 'C'. And is not left filled.
3. Full Binary Tree
   
   A 'Full Binary Tree' is a 'Binary Tree' in which every Node can have either have 2 children or no children. i.e. 1 child is not allowed.
   
   
   
4. Degenerate Binary Tree
   
   A 'Degenerate Binary Tree' is the 'Binary Tree' that can have only one child. The child can be the left or the right child.
   
   
   
5. Skewed Binary Tree
   
   A 'Skewed Binary Tree' is a 'Degenerate Binary Tree' in which the tree can have only one child.
   
   But if the Parent Node has a left Child, all the Nodes in the tree must have the left Child.
   
   Left Skewed Binary Tree Example :
   
   
   
   
   
   Right Skewed Binary Tree Example :
   
   
   
6. Balanced Binary Tree
   
   What is the exact thing that comes to your mind, when we say a 'Balanced Binary Tree' ?
   
   Well ! A Binary Tree that is Balanced.
   
   Now, to check if a Binary Tree is balanced or not. We need to check the depth of left and right sub tree of the parent element.
   
   And if the difference of depth is 0 or 1, it is a 'Balanced Binary Tree', else it is not.
   
   Let us clear it with the below example :
   
   
   
   
   
   Now, what is the depth of the left sub tree of Parent Node 'A'?
   
   The left sub tree of Parent Node 'A' is,
   
   
   
   
   
   And the depth of 'B' is 1.
   
   Next, let us calculate the depth of the right sub tree of Parent Node 'A'.
   
   The right sub tree of Parent Node 'A' is,
   
   
   
   
   
   And the depth of 'C' is 2.
   
   Now, if we find the difference between 2 and 1.
   
   
   2-1 = 1
   
   
   And the difference is 1. So the above tree is a 'Balanced Binary Tree'.
   
   Now let us take another example :
   
   
   
   
   
   Similarly, let us calculate the depth of the left sub tree of Parent Node 'A'.
   
   The left sub tree of Parent Node 'A' is,
   
   
   
   
   
   And the depth of 'B' is 1.
   
   Next, let us calculate the depth of the right sub tree of Parent Node 'A'.
   
   The right sub tree of Parent Node 'A' is,
   
   
   
   
   
   And the depth of 'C' is 3.
   
   Now, if we find the difference between 3 and 1.
   
   
   3-1 = 2
   
   
   And the difference is 2. So the above tree is a not a 'Balanced Binary Tree'.