Check whether Binary Tree is Heap or Not.
Difference between en4 and en5, changed 4 character(s)
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.↵


History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English KrishKanani148 2023-02-03 20:16:14 4 (published)
en4 English KrishKanani148 2023-02-03 20:15:09 0 (saved to drafts)
en3 English KrishKanani148 2023-02-03 20:14:32 11 Tiny change: '.\n~~~~~\n\n#include' -> '.\n~~~~~\nCode in C++\n#include'
en2 English KrishKanani148 2023-02-03 20:13:39 2 Tiny change: '.\n~~~~~\n#include' -> '.\n~~~~~\n\n#include'
en1 English KrishKanani148 2023-02-03 20:12:26 6267 Initial revision (published)