Check if a given Binary Tree is Heap

#include <bits/stdc++.h>

using namespace std;


struct Node
{
	int key;
	struct Node *left;
	struct Node *right;
};


struct Node *newNode(int k)
{
	struct Node *node = new Node;
	node->key = k;
	node->right = node->left = NULL;
	return node;
}

unsigned int countNodes(struct Node* root)
{
	if (root == NULL)
		return (0);
	return (1 + countNodes(root->left)
			+ countNodes(root->right));
}


bool is_complete_tree (struct Node* root,
					unsigned int index,
					unsigned int number_nodes)
{

	if (root == NULL)
		return (true);


	if (index >= number_nodes)
		return (false);

	return (is_complete_tree(root->left, 2*index + 1,
						number_nodes) &&
			is_complete_tree(root->right, 2*index + 2,
						number_nodes));
}

bool is_heap_property(struct Node* root)
{
	
	if (root->left == NULL && root->right == NULL)
		return (true);


	if (root->right == NULL)
	{
		return (root->key >= root->left->key);
	}
	else
	{

		if (root->key >= root->left->key &&
			root->key >= root->right->key)
			return ((is_heap_property(root->left)) &&
					(is_heap_property(root->right)));
		else
			return (false);
	}
}


bool isHeap(struct Node* root)
{

	unsigned int node_count = countNodes(root);
	unsigned int index = 0;

	if (is_complete_tree(root, index,
					node_count)
		&& is_heap_property(root))
		return true;
	return false;
}

int main()
{
	struct Node* root = NULL;
	root = newNode(25);
	root->left = newNode(11);
	root->right = newNode(16);
	root->left->left = newNode(3);
	root->left->right = newNode(8);

	if (isHeap(root))
		cout << "Given Binary Tree is a Max - Heap\n";
	else
		cout << "Given Binary Tree is not a Max - Heap\n";

	return 0;
}

class Node {
	int key;
	Node left, right;

	Node(int k)
	{
		key = k;
		left = right = null;
	}
}

class Is_BinaryTree_MaxHeap
{

	int countNodes(Node root)
	{
		if (root == null)
			return 0;
		return (1 + countNodes(root.left)
				+ countNodes(root.right));
	}

	boolean isCompleteUtil(Node root, int index,
						int number_nodes)
	{

		if (root == null)
			return true;


		if (index >= number_nodes)
			return false;


		return isCompleteUtil(root.left,
							2 * index + 1,
							number_nodes)
			&& isCompleteUtil(root.right,
							2 * index + 2,
							number_nodes);
	}


	boolean isHeapUtil(Node root)
	{

		if (root.left == null && root.right == null)
			return true;


		if (root.right == null) {

			return root.key >= root.left.key;
		}
		else {

			if (root.key >= root.left.key
				&& root.key >= root.right.key)
				return isHeapUtil(root.left)
					&& isHeapUtil(root.right);
			else
				return false;
		}
	}


	boolean isHeap(Node root)
	{
		if (root == null)
			return true;

		int node_count = countNodes(root);

		if (isCompleteUtil(root, 0, node_count) == true
			&& isHeapUtil(root) == true)
			return true;
		return false;
	}


	public static void main(String args[])
	{
		Is_BinaryTree_MaxHeap bt
			= new Is_BinaryTree_MaxHeap();

		Node root = new Node(10);
		root.left = new Node(9);
		root.right = new Node(8);
		root.left.left = new Node(7);
		root.left.right = new Node(6);
		root.right.left = new Node(5);
		root.right.right = new Node(4);
		root.left.left.left = new Node(3);
		root.left.left.right = new Node(2);
		root.left.right.left = new Node(1);

		if (bt.isHeap(root) == true)
			System.out.println(
				"Given Binary Tree is a Max-Heap");
		else
			System.out.println(
				"Given Binary Tree is not a Max-Heap");
	}
}

class binary_tree:
	def __init__(self, value):
		self.key = value
		self.left = None
		self.right = None

	def count_nodes(self, root):
		if root is None:
			return 0
		else:
			return (1 + self.count_nodes(root.left) + self.count_nodes(root.right))

	def is_heap_property(self, root):

		if (root.left is None and
				root.right is None):
			return True

		if root.right is None:
			return root.key >= root.left.key
		else:
			if (root.key >= root.left.key and
					root.key >= root.right.key):
				return (self.is_heap_property(root.left) and self.is_heap_property(root.right))
			else:
				return False

	def is_complete_tree(self, root,
						index, node_count):
		if root is None:
			return True
		if index >= node_count:
			return False
		return (self.is_complete_tree(root.left, 2 * index + 1, node_count) and self.is_complete_tree(root.right, 2 * index + 2, node_count))

	def isHeap(self):
		node_count = self.count_nodes(self)
		if (self.is_complete_tree(self, 0, node_count) and self.is_heap_property(self)):
			return True
		else:
			return False


root = binary_tree(25)
root.left = binary_tree(11)
root.right = binary_tree(16)
root.left.left = binary_tree(3)
root.left.right = binary_tree(8)

if root.isHeap():
	print("Given Binary Tree is a Max - Heap")
else:
	print("Given Binary Tree is not a Max - Heap")