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 at Prepbytes.