How To Check if a binary tree is a min-heap or not ?

Given a binary tree, check if it is a min-heap or not. In order words, the binary tree must be a complete binary tree where each node has value is greater than the value of its parent.
 
For example, below binary tree is a min-heap.
Min Heap.JPG
while below binary tree is not a min-heap.
BST.JPG

1. Recursive solution

 
The idea is to traverse the tree in preorder fashion. The value of each encountered node should be less than its left or right child. If that is not the case for every internal node, the binary tree is not a min-heap.
To check for a complete binary tree, the index of left and right child for any node is less than number of nodes for every node. We can pass index as a parameter in recursion and check for every node that their left and right child’s index are within correct range.
The algorithm can be implemented in such a way that both these properties can be checked in a single tree traversal. This is demonstrated below in C++ and Java:
Output:

Given Binary Tree is a min-Heap
 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(h) for recursion call stack where h is the height of the binary tree.

2. Iterative solution

 
The idea is to perform Level order traversal for the given binary tree to check both structural and heap properties of a min-heap.
  1. To check for the structural property, simply check that no non-empty child is encountered for any node once an empty child is seen.
     
  2. To check for the heap propery, simply check that both left and right child are greater than the parent node. This can be easily done while inserting the childrens to the queue.
 
Here’s C++ and Java program that demonstrates it:
Output:

Given Binary Tree is a min-Heap
 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(n) for level order traversal where n is the number of nodes in the binary tree.
 
Exercise: Modify the solution to check the binary tree for max-heap.