Check if a given Binary Tree is Heap

Problem Statement:

Given a binary tree, our task is to check whether the given tree follows the max heap property or not.

What is a Binary Tree?

Binary tree is a type of Tree data structure in which every node in the tree will have 2 or less than 2 child nodes and those child nodes will be termed as the left child and the right child of the node.

What is a Max-Heap?

Max – Heap follows the property of a complete binary tree in which the value of the internal node is greater than or equal to the value of the children of that node.
Examples of Max Heap:

There are two conditions that should be fulfilled for satisfying the max-heap property:

  • It must be a complete binary tree, i.e. except for the last level of the tree, all other levels must be fully filled with nodes.
  • The value of every node must be greater than or equal to their children. (condition for max – heap).

We have to check the above conditions separately, we build the is_complete_tree function for checking whether the tree is a complete binary tree or not, and is_heap_property for checking the max – heap properties.

Following will be the procedure for implementing the Is_complete_tree function:

  • Firstly, calculate the number of nodes in the binary tree.
  • Make the recursion call from the root of the binary tree with index i having an initial value of 0, and the count of nodes present in the binary tree.
  • If the current node is NULL, then the given tree is a complete binary tree.
  • If the ith index of the current node is greater than or equal to the number of nodes present in the binary tree, then it is not a complete binary tree and returns false.
  • Check recursively for the left and right sub – tree for the same conditions. For the left sub – tree change the value of the index to (2 i + 1) and for the right subtree change the value of the index to (2 i + 2).

Following will be the procedure for implementing the is_heap_property function:

  • Every node can have 2 child nodes, 0 child nodes (if it is a leaf node), or 1 child node (it is only possible for at most 1 such node).
  • If there is no child node present for the given node, then return true.
  • If the node has 1 child node, it must be the left child node for following the complete binary tree condition. We have to compare the given node to its single child node only.
  • If there are 2 child nodes present for the given node, then check the heap property at the node at recursion for both sub-trees.

Code Implementation

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

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


struct Node* newNode(int k)
{
	struct Node* node
		= (struct Node*)malloc(sizeof(struct 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 isCompleteUtil(struct Node* root,
					unsigned int index,
					unsigned 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));
}


bool isHeapUtil(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 ((isHeapUtil(root->left))
					&& (isHeapUtil(root->right)));
		else
			return (false);
	}
}


bool isHeap(struct Node* root)
{

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

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


int main()
{
	struct Node* root = NULL;
	root = newNode(10);
	root->left = newNode(9);
	root->right = newNode(8);
	root->left->left = newNode(7);
	root->left->right = newNode(6);
	root->right->left = newNode(5);
	root->right->right = newNode(4);
	root->left->left->left = newNode(3);
	root->left->left->right = newNode(2);
	root->left->right->left = newNode(1);

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

	return 0;
}
#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")


Output:
Given Binary Tree is a Max-Heap

This article tried to discuss How to Check if a given Binary Tree is Heap. Hope this blog helps you understand the concept. To practice more problems feel free to check MYCODE | Competitive Programming at Prepbytes.

Leave a Reply

Your email address will not be published. Required fields are marked *