Binary Tress - Types and Properties
๐ณ What is a Binary Tree?
A binary tree is a special type of tree where each node has at most two children:
-
Left child
-
Right child
✅ It is hierarchical and recursive in nature.
๐ฅ Types of Binary Trees
There are several special types of binary trees based on structure:
1. Full Binary Tree
-
Every node has 0 or 2 children. (No node with only 1 child)
2. Complete Binary Tree
-
All levels are completely filled except possibly the last level, which is filled from left to right.
3. Perfect Binary Tree
It is a full binary tree where all leaf nodes are at the same level.
Perfect Binary Tree: A perfect binary tree is a full binary tree where all leaf nodes are at the same level, resulting in a completely filled and balanced structure. A perfect binary tree is always a full binary tree and a complete binary tree.
It is a full binary tree where all leaf nodes are at the same level.
4. Balanced Binary Tree
-
The height difference between left and right subtree for every node is at most 1.
Examples: AVL Tree, Red-Black Tree.
5. Degenerate (or Skewed) Tree
-
Every parent has only one child.
Two types:
-
Left-skewed tree (only left child)
-
Right-skewed tree (only right child)
๐ต Summary Table
| Type of Tree | Key Characteristics |
|---|---|
| Full Binary Tree | 0 or 2 children only |
| Perfect Binary Tree | Full + all leaves at same level |
| Complete Binary Tree | All levels full except last, filled left to right |
| Balanced Binary Tree | Height balanced |
| Degenerate Tree | Like a linked list |
๐ Important Properties of Binary Trees
1. Maximum number of nodes at level i
At level i (root is level 0), the maximum number of nodes = 2แถฆ.
Example:
Level 0 → 1 node
Level 1 → 2 nodes
Level 2 → 4 nodes
Level 3 → 8 nodes, and so on.
2. Maximum number of nodes in a binary tree of height h
Maximum nodes = 2^(h+1) - 1
where h = height of the tree (root is height 0).
Example:
Height 2 → Maximum 2³ - 1 = 7 nodes.
3. Minimum possible height (h) of a binary tree with n nodes
Minimum height = ⌈log₂(n+1)⌉ - 1
where ⌈ ⌉ is the ceiling function (round up).
Example:
Ifn = 7nodes → height = ⌈log₂(8)⌉ - 1 = 3 - 1 = 2
4. In a perfect binary tree:
-
Number of leaf nodes = (number of internal nodes) + 1
-
Total nodes = 2 × (number of leaf nodes) - 1
Example:
4 leaf nodes → Total nodes = 2×4 -1 = 7 nodes.
5. Relationship between number of leaf nodes (L) and total nodes (N)
In a full binary tree:
-
L = (N + 1) / 2
-
Internal nodes = (N - 1) / 2
Example:
N = 7 →
L = (7+1)/2 = 4 leaves,
Internal = (7-1)/2 = 3 internal nodes.
6. A binary tree with n nodes has exactly n-1 edges
Each node (except root) connects to its parent by one edge.
7. Traversals (important algorithms)
-
Inorder (Left, Root, Right) — used for BST sorted order.
-
Preorder (Root, Left, Right) — used to create a copy of the tree.
-
Postorder (Left, Right, Root) — used to delete the tree.
8. Types of binary trees
-
Full Binary Tree
-
Perfect Binary Tree
-
Complete Binary Tree
-
Balanced Binary Tree
-
Degenerate Tree
Each has specific structural properties (which we already discussed earlier).
๐ต Quick Summary Table
| Property | Formula |
|---|---|
Max nodes at level i | 2แถฆ |
Max total nodes of height h | 2^(h+1) - 1 |
Min height with n nodes | ⌈log₂(n+1)⌉ - 1 |
| Leaf nodes in perfect tree | Internal nodes + 1 |
| Edges in binary tree | n - 1 |
Comments
Post a Comment