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.