Given a root of Binary tree we need to check whether the binary tree is a Heap or not ↵
NOTE: here Heap means Max-Heap.↵
↵
What is Heap?↵
↵
_Heap is a data structure which is a complete binary tree._↵
↵
It's a complete binary tree↵
It follows either a max-heap or min-heap property. A max-heap is a binary tree where the parent node is always greater than or equal to its child nodes.↵
↵
A complete binary tree is a type of binary tree in which every level, except possibly the last level, is completely filled and all nodes are left-justified. In a complete binary tree, all leaf nodes will be on the same level and this level has the maximum number of nodes. The last node in a complete binary tree is always a left node.↵
↵
**Input:** 10 8 9 5 5 4 5 1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1↵
**Output:** True↵
**Explanation:** In max Heap all the parent nodes value must be greater than their childs nodes value. Our Binary Tree is:↵
Parent node 10, left child = 8 and right child = 9,↵
Parent node 8, left child = 5 and right child = 5,↵
Parent node 9, left child = 4 and right child = 5,↵
Parent node 5, left child = 1 and right child = 2↵
It is complete Binary tree and all the child nodes of their respective parents are smaller.↵
↵
~~~~~↵
Code in C++↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
// Tree Node↵
struct Node {↵
int data;↵
Node *left;↵
Node *right;↵
↵
Node(int val) {↵
data = val;↵
left = right = NULL;↵
}↵
};↵
↵
// Function to Build Tree↵
Node *buildTree(string str) {↵
↵
if (str.length() == 0 || str[0] == 'N') return NULL;↵
↵
// Creating vector of strings from input↵
vector<string> ip;↵
↵
istringstream iss(str);↵
for (string str; iss >> str;) ip.push_back(str);↵
↵
Node *root = new Node(stoi(ip[0]));↵
↵
// Push the root to the queue↵
queue<Node *> queue;↵
queue.push(root);↵
↵
// Starting from the second element↵
int i = 1;↵
while (!queue.empty() && i < ip.size()) {↵
↵
// Get and remove the front of the queue↵
Node *currNode = queue.front();↵
queue.pop();↵
↵
// Get the current Node's value from the string↵
string currVal = ip[i];↵
↵
// If the left child is not null↵
if (currVal != "N") {↵
↵
// Create the left child for the current Node↵
currNode->left = new Node(stoi(currVal));↵
↵
// Push it to the queue↵
queue.push(currNode->left);↵
}↵
↵
// For the right child↵
i++;↵
if (i >= ip.size()) break;↵
currVal = ip[i];↵
↵
// If the right child is not null↵
if (currVal != "N") {↵
↵
// Create the right child for the current Node↵
currNode->right = new Node(stoi(currVal));↵
↵
// Push it to the queue↵
queue.push(currNode->right);↵
}↵
i++;↵
}↵
↵
return root;↵
}↵
↵
class Solution {↵
private:↵
↵
//Function to count the number of nodes of the tree↵
int countNodes(struct Node* root)↵
{↵
if(root == NULL)↵
return 0;↵
↵
int ans = 1 + countNodes(root->left) + countNodes(root->right);↵
return ans;↵
}↵
↵
//Function to check that the tree is complete Binary Tree.↵
bool isCBT(struct Node* root, int index, int count)↵
{↵
if(root == NULL) //If root null return true.↵
return true;↵
↵
//If the index exceed count that mean that the tree is not CBT ↵
if(index >= count)↵
return false;↵
else↵
{↵
bool left = isCBT(root->left, 2*index + 1, count);↵
bool right = isCBT(root->right, 2*index + 2, count);↵
↵
return left && right;↵
}↵
}↵
↵
//Function to check the Complete Binary tree is Max Heap or not.↵
bool isMaxHeap(struct Node* root)↵
{↵
//Leaf Node↵
if(root->left == NULL && root->right == NULL)↵
return true;↵
↵
// One Node (Left node)↵
if(root->right == NULL)↵
return (root->data > root->left->data);↵
else //Both node↵
{↵
bool left = isMaxHeap(root->left);↵
bool right = isMaxHeap(root->right);↵
↵
return left && right && (root->data > root->left->data && root->data > root->right->data);↵
}↵
}↵
public:↵
bool isHeap(struct Node* tree) {↵
int index = 0;↵
int totalCount = countNodes(tree);↵
↵
if(isCBT(tree, index, totalCount) && isMaxHeap(tree))↵
return true;↵
↵
return false;↵
}↵
};↵
↵
int main() {↵
int tc;↵
scanf("%d ", &tc);↵
while (tc--) {↵
string treeString;↵
getline(cin, treeString);↵
Solution ob;↵
Node *root = buildTree(treeString);↵
if (ob.isHeap(root))↵
cout << 1 << endl;↵
else↵
cout << 0 << endl;↵
}↵
↵
return 0;↵
}↵
~~~~~↵
↵
Function Explained↵
------------------↵
**isCBT() Function Explanation:** The function first checks if the tree is a complete binary tree by calling the isCBT() function which takes 3 arguments, the root of the tree, an index and count of total nodes. The _function checks if the tree is a complete binary tree_ by traversing the tree using the index and count values. The function returns true if the tree is a complete binary tree, otherwise it returns false.↵
↵
**isMaxHeap() Function Explanation:** Next, the function checks if the tree follows the max-heap property by calling the isMaxHeap() function which takes the root of the tree as an input. The _function checks the max-heap property by recursively traversing the tree_, checking if the parent node is greater than or equal to its child nodes. The function returns true if the tree follows the max-heap property, otherwise it returns false.↵
↵
**isHeap() Function Explanation:** Finally, the isHeap() function checks _if both isCBT() and isMaxHeap() functions return true_, indicating that the given tree is both a complete binary tree and follows the max-heap property. If both conditions are true, the function returns true, otherwise it returns false.↵
↵
↵
NOTE: here Heap means Max-Heap.↵
↵
What is Heap?↵
↵
_Heap is a data structure which is a complete binary tree._↵
↵
It's a complete binary tree↵
It follows either a max-heap or min-heap property. A max-heap is a binary tree where the parent node is always greater than or equal to its child nodes.↵
↵
A complete binary tree is a type of binary tree in which every level, except possibly the last level, is completely filled and all nodes are left-justified. In a complete binary tree, all leaf nodes will be on the same level and this level has the maximum number of nodes. The last node in a complete binary tree is always a left node.↵
↵
**Input:** 10 8 9 5 5 4 5 1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1↵
**Output:** True↵
**Explanation:** In max Heap all the parent nodes value must be greater than their childs nodes value. Our Binary Tree is:↵
Parent node 10, left child = 8 and right child = 9,↵
Parent node 8, left child = 5 and right child = 5,↵
Parent node 9, left child = 4 and right child = 5,↵
Parent node 5, left child = 1 and right child = 2↵
It is complete Binary tree and all the child nodes of their respective parents are smaller.↵
↵
~~~~~↵
Code in C++↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
// Tree Node↵
struct Node {↵
int data;↵
Node *left;↵
Node *right;↵
↵
Node(int val) {↵
data = val;↵
left = right = NULL;↵
}↵
};↵
↵
// Function to Build Tree↵
Node *buildTree(string str) {↵
↵
if (str.length() == 0 || str[0] == 'N') return NULL;↵
↵
// Creating vector of strings from input↵
vector<string> ip;↵
↵
istringstream iss(str);↵
for (string str; iss >> str;) ip.push_back(str);↵
↵
Node *root = new Node(stoi(ip[0]));↵
↵
// Push the root to the queue↵
queue<Node *> queue;↵
queue.push(root);↵
↵
// Starting from the second element↵
int i = 1;↵
while (!queue.empty() && i < ip.size()) {↵
↵
// Get and remove the front of the queue↵
Node *currNode = queue.front();↵
queue.pop();↵
↵
// Get the current Node's value from the string↵
string currVal = ip[i];↵
↵
// If the left child is not null↵
if (currVal != "N") {↵
↵
// Create the left child for the current Node↵
currNode->left = new Node(stoi(currVal));↵
↵
// Push it to the queue↵
queue.push(currNode->left);↵
}↵
↵
// For the right child↵
i++;↵
if (i >= ip.size()) break;↵
currVal = ip[i];↵
↵
// If the right child is not null↵
if (currVal != "N") {↵
↵
// Create the right child for the current Node↵
currNode->right = new Node(stoi(currVal));↵
↵
// Push it to the queue↵
queue.push(currNode->right);↵
}↵
i++;↵
}↵
↵
return root;↵
}↵
↵
class Solution {↵
private:↵
↵
//Function to count the number of nodes of the tree↵
int countNodes(struct Node* root)↵
{↵
if(root == NULL)↵
return 0;↵
↵
int ans = 1 + countNodes(root->left) + countNodes(root->right);↵
return ans;↵
}↵
↵
//Function to check that the tree is complete Binary Tree.↵
bool isCBT(struct Node* root, int index, int count)↵
{↵
if(root == NULL) //If root null return true.↵
return true;↵
↵
//If the index exceed count that mean that the tree is not CBT ↵
if(index >= count)↵
return false;↵
else↵
{↵
bool left = isCBT(root->left, 2*index + 1, count);↵
bool right = isCBT(root->right, 2*index + 2, count);↵
↵
return left && right;↵
}↵
}↵
↵
//Function to check the Complete Binary tree is Max Heap or not.↵
bool isMaxHeap(struct Node* root)↵
{↵
//Leaf Node↵
if(root->left == NULL && root->right == NULL)↵
return true;↵
↵
// One Node (Left node)↵
if(root->right == NULL)↵
return (root->data > root->left->data);↵
else //Both node↵
{↵
bool left = isMaxHeap(root->left);↵
bool right = isMaxHeap(root->right);↵
↵
return left && right && (root->data > root->left->data && root->data > root->right->data);↵
}↵
}↵
public:↵
bool isHeap(struct Node* tree) {↵
int index = 0;↵
int totalCount = countNodes(tree);↵
↵
if(isCBT(tree, index, totalCount) && isMaxHeap(tree))↵
return true;↵
↵
return false;↵
}↵
};↵
↵
int main() {↵
int tc;↵
scanf("%d ", &tc);↵
while (tc--) {↵
string treeString;↵
getline(cin, treeString);↵
Solution ob;↵
Node *root = buildTree(treeString);↵
if (ob.isHeap(root))↵
cout << 1 << endl;↵
else↵
cout << 0 << endl;↵
}↵
↵
return 0;↵
}↵
~~~~~↵
↵
Function Explained↵
------------------↵
**isCBT() Function Explanation:** The function first checks if the tree is a complete binary tree by calling the isCBT() function which takes 3 arguments, the root of the tree, an index and count of total nodes. The _function checks if the tree is a complete binary tree_ by traversing the tree using the index and count values. The function returns true if the tree is a complete binary tree, otherwise it returns false.↵
↵
**isMaxHeap() Function Explanation:** Next, the function checks if the tree follows the max-heap property by calling the isMaxHeap() function which takes the root of the tree as an input. The _function checks the max-heap property by recursively traversing the tree_, checking if the parent node is greater than or equal to its child nodes. The function returns true if the tree follows the max-heap property, otherwise it returns false.↵
↵
**isHeap() Function Explanation:** Finally, the isHeap() function checks _if both isCBT() and isMaxHeap() functions return true_, indicating that the given tree is both a complete binary tree and follows the max-heap property. If both conditions are true, the function returns true, otherwise it returns false.↵
↵
↵