Binary Tree: Check if a binary tree is a min heap
Write a program to check if a given binary tree is a Min-Heap or not.
Properties of Min-Heap
A Min-Heap is a complete binary tree in which the value in each node is smaller than or equal to the values in the children of that node. So as per this property the root node of the binary tree will hold the smallest value of all the nodes.
To check if a Binary Tree is a Min-Heap,
- we have to first check if the given binary tree is a complete Binary Tree and
- also check if all the nodes follow the above-given property that the parent is smaller than both of its children.
To check if a Binary Tree is Complete we traverse through the tree using BFS and then check if non-null nodes are present after the first null node if present then the tree is not a Complete Binary Tree
Algorithm
isMinHeap(node):
- If node == null, Return true
- Return isCompleteTree(node) && isMinHeapCall(node)
isCompleteTree(node):
- If node == null, Return true
- Create a Queue named nodesQueue for BFS
- Add the node in the nodesQueue
- Create a variable named isHeapEnded and initialize it to false
- While nodesQueue is not empty:
- Pop the front element from the queue and store it in currentNode
- If currentNode is null:
- isHeapEnded = true
- Else:
- If isHeapEnded is true, Return false
- Add the left and right nodes of currentNode to the nodesQueue
- Return true
isMinHeapCall(node):
- If the node is null, Return true as an empty tree is considered a Min Heap
- If node.left is not null and node.left.value < node.value:
- Return false
- If node.right is not null and node.right.value < node.value:
- Return false
- Return isMinHeapCall(node.left) && isMinHeapCall(node.right)
Complexity
Time Complexity: O(N)
Space Complexity: O(N)
The Time Complexity will be O(N) as we have to visit and check each node and the space complexity is O(N) as to check if the tree isCompleteTree we have to store the nodes.
Diagram
Java Code
import java.util.LinkedList;
import java.util.Queue;
class BinaryTreeCheckForMinHeap{
static class Node {
int value;
Node left, right;
Node(int value) {
this.value = value;
this.left = null;
this.right = null;
}
}
public static boolean isMinHeap(Node node) {
// an empty tree is considered as a min heap
if (node == null) {
return true;
}
// We have to check two conditions:
// 1. The Given Binary Tree is Complete
// 2. The Given Binary Tree follows the Min Heap Property
return (isCompleteTree(node) && isMinHeapCall(node));
}
public static boolean isCompleteTree(Node node) {
// empty tree is considered as a complete binary tree
if (node == null) {
return true;
}
// Do a BFS traversal for the binary tree and check if it is complete or not
Queue nodesQueue = new LinkedList();
nodesQueue.add(node);
boolean isHeapEnded = false;
while (nodesQueue.size() > 0) {
Node currentNode = nodesQueue.poll();
if (currentNode == null) {
// When we get the first null node, then it should be end of the heap
// All the nodes after we get first null node should be also null
isHeapEnded = true;
} else {
if (isHeapEnded) {
// If we get a node which is not null after getting a null node then it
// cannot be a complete binary tree
return false;
}
nodesQueue.add(currentNode.left);
nodesQueue.add(currentNode.right);
}
}
// If we are out of the loop then the binary tree is a complete tree
return true;
}
public static boolean isMinHeapCall(Node node) {
// Base Case: Since a null node is a empty min heap
if (node == null) {
return true;
}
if (node.left != null && node.left.value < node.value) {
// Return false, as left child has value less than the parent
return false;
}
if (node.right != null && node.right.value < node.value) {
// Return false, as right child has value less than the parent
return false;
}
// Check both the child nodes recursively
return (isMinHeapCall(node.left) && isMinHeapCall(node.right));
}
public static void main(String[] args) {
// Example 1: A Min Heap
Node tree1 = new Node(1);
tree1.left = new Node(3);
tree1.right = new Node(2);
tree1.left.left = new Node(4);
tree1.left.right = new Node(6);
tree1.right.left = new Node(5);
if (isMinHeap(tree1)) {
System.out.println("The Example 1 is a MinHeap");
} else {
System.out.println("The Example 1 is not a MinHeap");
}
// Example 2: A complete tree but not a min heap
Node tree2 = new Node(8);
tree2.left = new Node(2);
tree2.right = new Node(6);
tree2.left.left = new Node(12);
tree2.left.right = new Node(11);
tree2.right.left = new Node(10);
if (isMinHeap(tree2)) {
System.out.println("The Example 2 is a MinHeap");
} else {
System.out.println("The Example 2 is not a MinHeap");
}
// Example 2: A Non Complete Binary tree
// In the below tree tree3.left.left is null so it is not a complete binary tree.
Node tree3 = new Node(1);
tree3.left = new Node(2);
tree3.right = new Node(3);
tree3.left.right = new Node(4);
tree3.right.left = new Node(5);
if (isMinHeap(tree3)) {
System.out.println("The Example 3 is a MinHeap");
} else {
System.out.println("The Example 3 is not a MinHeap");
}
}
}
Output
The Example 1 is a MinHeap
The Example 2 is not a MinHeap
The Example 3 is not a MinHeap
Thanks for feedback.