- Types of Binary Trees :-
1) Rooted Binary Tree :
.png)
-A rooted binary tree is a binary tree that satisfies the following 2 properties-
It has a root node.
- Each node has at most 2 children.
- No matter what type of Binary tree it is, it will always be a Rooted Binary Tree
.png)
2) Fully/Strictly Binary Tree :
.png) |
- A binary tree in which every node has either 0 or 2 children is called as a Full binary tree.
- Full binary tree is also called as Strictly binary tree.
- First tree is not a full binary tree, because C only has 1 child
3)Complete/Perfect Binary Tree :
.png) |
-A complete binary tree is a binary tree that satisfies the following 2 properties-
1)Every internal node has exactly 2 children.
2)All the leaf nodes are at the same level.
-First tree is not a full Binary tree because not all leaf nodes are at the same level .
4) Almost Complete Binary Tree :
.png) |
-An almost complete binary tree is a binary tree that satisfies the following 2 properties-
1)All the levels are completely filled except possibly the last level.
2)The last level must be strictly filled from left to right.
-First tree is not an almost complete binary tree because the last level is not filled from left to right .
5) Skewed Binary Tree :
.png)
-A skewed binary tree is a binary tree that satisfies the following 2 properties-
All the nodes except one node has one and only one child.
- The remaining node has no child.
- A skewed binary tree is a binary tree of n nodes such that its depth is (n-1).
Binary Tree Properties :
-Property 1:
Minimum number of nodes in a binary tree of height H = H + 1
-Property 2:
Maximum number of nodes in a binary tree of height H = 2H+1 – 1
-Property 3:
Total Number of leaf nodes in a Binary Tree = Total Number of nodes with 2 children + 1
-Property 4:
Maximum number of nodes at any level ‘L’ in a binary tree = 2L