Before we proceed, we first know what BT really is? Binary Tree is a type of data structure that is hierarchical in nature. A BT is represented by nodes where every node has left, a right pointer, and data as the weight of node. Each node can contain a maximum of 2 children which refer to the left and right child of a parent node.
Why we need Binary Trees? | Why we use binary Trees?
- Using BT we can do fast search, insertion, and deletion on data(given in some priority order… like BST).
- Using BT we can also find the closest item.
- Store the data in a hierarchical manner(Ex. File system in the computer).
- Implement BT using pointer which takes less time to perform any action.
- Implement dictionaries with prefix lookup.
- Fast search in the fixed text of the given dataset.
Properties of Binary Trees
- Maximum number of nodes at any level: 2^L where L is a number of levels (0<=L<=H).
- Minimum and maximum number of nodes in a BT of height H: Minimum- H+1 and Maximum- 2^(H+1) – 1 where level 0 as height 0.
- Minimum possible height of a given BT having N nodes: log2(N+1)-1 where level 0 as height 0.
- Total number of leaf nodes: Total number of nodes with 2 children + 1.
- Minimum number of levels of a BT having L leaf nodes: (log2 L) +1.
Types of Binary Trees
Full Binary Trees
A Binary Tree whose root and intermediate nodes have 2 child nodes. In other words, we can also say that except leaf nodes every node has 2 child nodes.
Note: Number of leaf nodes in a full binary tree: Number of internal nodes+1.
Complete Binary Tree
A Binary Tree whose all levels except the last level are totally filled and all nodes are filled from left to right
Note: Binary Heap is an example of a complete binary tree.
Perfect Binary Tree
A Binary Tree whose internal nodes and root node have 2 children and all leaf at the same level.
Note: Total number of nodes in Perfect Binary Tree: 2^H -1 where H is the height of BT.
Balanced Binary Tree
A Binary Tree whose left subtree height h1 and right subtree height h2 then |h1-h2| <= 1.
Note: AVL and R-B tree maintain a balanced binary tree.
Pathological Binary Tree (Skewed BT/ Degenerate BT)
A Binary Tree whose all internal nodes have only one child may be left child or it may be a right child.
Note: Pathological BT Height: Number of nodes-1.