Write a function that checks whether a given binary tree is a Max heap.

A Binary tree need to fulfill the following two conditions for being a heap:

• It should be a complete tree (i.e. all levels except last should be full).
• Every node's value should be greater than or equal to its child node.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include<conio.h>
#include "Btree.h"


/* This function counts the number of nodes in a binary tree */
int countNodes(Btree root)
{
	if (root == NULL)
		return 0;
	return (1 + countNodes(root->left) + countNodes(root->right));
}

/* This function checks if the binary tree is complete or not */
int isCompleteUtil(Btree root,  int index, int number_nodes)
{
	// An empty tree is complete
	if (root == NULL)
		return 1;

	// If index assigned to current node is more than
	// number of nodes in tree, then tree is not complete
	if (index >= number_nodes)
		return 0;

	// Recur for left and right subtrees
	return (isCompleteUtil(root->left, 2 * index + 1, number_nodes) &&
		isCompleteUtil(root->right, 2 * index + 2, number_nodes));
}

// This Function checks the heap property in the tree.
int isHeapUtil(Btree root)
{
	//  Base case : single node satisfies property
	if (root->left == NULL && root->right == NULL)
		return 1;

	//  node will be in second last level
	if (root->right == NULL)
	{
		//  check heap property at Node
		//  No recursive call , because no need to check last level
		return (root->data >= root->left->data);
	}
	else
	{
		//  Check heap property at Node and
		//  Recursive check heap property at left and right subtree
		if (root->data >= root->left->data &&
			root->data >= root->right->data)
			return ((isHeapUtil(root->left)) &&
			(isHeapUtil(root->right)));
		else
			return 0;
	}
}

//  Function to check binary tree is a Heap or Not.
int isHeap(Btree root)
{
	// These two are used in isCompleteUtil()
	unsigned int node_count = countNodes(root);
	unsigned int index = 0;

	if (isCompleteUtil(root, index, node_count) && isHeapUtil(root))
		return 1;
	return 0;
}


void main()
{

	Btree B = Construct(10,
		Construct(8,
			Construct(6,
				NULL,
				NULL),
			Construct(5,
				NULL,
				NULL)),
		Construct(9,
			Construct(2,
				NULL,
				NULL),
			Construct(-2,
				NULL,
				NULL)));

	if (isHeap(B))
		printf("Given binary tree is a Heap\n");
	else
		printf("Given binary tree is not a Heap\n");

	getch();
}