Binary trees can be categorised into multiple types based on the number of child nodes each node in the binary tree has and also based on the way nodes are ordered.
Types Based on Node Distribution
Full Binary Trees
A full binary tree is a binary tree in which each node either has 2 child nodes or no child nodes at all. For example the below binary tree is a kind of full binary tree. There are no nodes in the tree which has only one child. Every node either has 2 child nodes or no nodes at all.
Complete Binary Tree
A complete binary tree is a binary tree in which all the rows/layers are completely filled except possibly for the last row. In the last row, the nodes should be continuously filled from left to right. For example, the binary tree illustrated below is a complete binary tree.
Where as the binary tree shown below is not complete since in the last row, the nodes towards left are not continuous i.e., there is a gap between node D and node E.
Perfect Binary Tree
A perfect binary tree is a binary tree in which all the internal nodes have 2 children. Below is an example perfect binary tree.
Types Based on Node Ordering
Binary Heaps
Heaps (Min Heap/ Max Heap) are tree-based data structures with an ordering property between the parent and child nodes. In a Max Heap, the value of each parent node is greater than or equal to the values of its children nodes, while in a Min Heap, the value of each parent node is smaller than or equal to the values of its children nodes. Heaps are often used in priority queue implementations due to their ability to efficiently find and remove the maximum or minimum element. Below is an example binary tree where each each node’s value is greated than it’s child nodes values, making it a Max Heap.
Binary Search Trees
If in a binary tree, the left subtree of a node contains only nodes with keys lesser than the node’s key, and the right subtree contains only nodes with keys greater than the node’s key, it is a type of binary search tree (BST). This ordering property allows quick search, insertion, and deletion operations, making BSTs ideal for many search-based applications. Below is an example Binary Search Tree.