  Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email  Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Check if a given Binary Tree is Heap

Last Updated on December 14, 2022 by Prepbytes ### 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.