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):
  1. If node == null, Return true
  2. Return isCompleteTree(node) && isMinHeapCall(node)
isCompleteTree(node):
  1. If node == null, Return true
  2. Create a Queue named nodesQueue for BFS
  3. Add the node in the nodesQueue
  4. Create a variable named isHeapEnded and initialize it to false
  5. While nodesQueue is not empty:
    1. Pop the front element from the queue and store it in currentNode 
    2. If currentNode is null:    
      1. isHeapEnded = true
    3. Else:
      1. If isHeapEnded is true, Return false
      2. Add the left and right nodes of currentNode to the nodesQueue
  6. Return true
isMinHeapCall(node):
  1. If the node is null, Return true as an empty tree is considered a Min Heap
  2. If node.left is not null and node.left.value < node.value:
    1. Return false
  3. If node.right is not null and node.right.value < node.value:
    1. Return false
  4. 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.



Read More....
Check if a binary tree is symmetric or mirror of itself
Check if a binary tree is symmetric or mirror of itself - iterative
Create a mirror of binary tree - Iterative approach
Create a mirror of binary tree - Recursive approach
Find the height of binary tree - Iterative approach