Here is the detailed explanation of Binary Trees and its Types
A binary tree is a hierarchical data structure in which each node has at most two children, referred to as the left child and the right child.
• The structure of a binary tree is such that each node can have zero, one, or two children.
• The topmost node in a binary tree is called the root, and nodes with no children are called leaves.
• A binary tree is proper if each node has either zero or two children.
Types of Binary Tree:
Types of Binary Tree based on the number of children:
Binary trees are categorized based on the number of children each node can have. The main types of binary trees based on the number of children are:
Full Binary Tree (Proper Binary Tree):
- In a full binary tree, every node has either zero or two children.
- Every internal node (non-leaf node) has exactly two children.
- All leaves are at the same level.
- Example:
1
/ \
2 3
/ \ / \
4 5 6 7
Degenerate (or Pathological) Binary Tree:
- In a degenerate binary tree, each parent node has only one associated child node.
- It essentially behaves like a linked list data structure.
- It has a time complexity similar to linked lists for many operations.
- Example:
1
\
2
\
3
\
4
\
5
Skewed Binary Tree:
- A skewed binary tree is a type of degenerate binary tree where all nodes have one child except one.
- Can be either left-skewed or right-skewed depending on whether all nodes are leaning towards the left or right respectively.
- Example:
Here’s an example of a left-skewed binary tree:
1
/
2
/
3
/
4
here’s an example of a right-skewed binary tree:
1
\
2
\
3
\
4
Types of Binary Tree On the basis of the completion of levels:
Complete Binary Tree:
- In a complete binary tree, every level, except possibly the last, is completely filled, and all nodes are as left as possible.
- In other words, a complete binary tree is just like a full binary tree, but with the last level filled from left to right.
- It allows for efficient storage and representation.
- Examples:
1
/ \
2 3
/ \ / \
4 5 6 7
Perfect Binary Tree:
- In a perfect binary tree, all internal nodes have exactly two children, and all leaf nodes are at the same level.
- Every level of the tree is completely filled.
- Examples:
1
/ \
2 3
/ \ / \
4 5 6 7
Balanced Binary Tree:
- A balanced binary tree is a binary tree in which the height of the two subtrees of any node never differs by more than one.
- These trees optimize search and insertion operations.
- Examples:
1
/ \
2 3
/ \ / \
4 5 6 7
/ \
8 9