Heap: Check if given a binary tree is a Heap

Problem Statement:

You are given a binary tree, you need to check if the binary tree satisfies heap property or not.

Below are the conditions that needs to be satisfied for heap property:

1. It should be a complete tree, meaning every level of the tree is completely filled.

2. Every node value should be greater than or equal to the child node.

Example:

Input:

Output:

True

Solution : Using heap property

For the solution we will check if the node satisfies the max heap property.

If it satisfies, then return true else false.

Time Complexity: O(n)
Space Complexity: O(h)

Code Solution

#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Node 
{
public:
    int data;
    Node* left;
    Node* right;

    Node(int val) 
    {
        data = val;
        left = right = NULL;
    }
};

bool solution(Node* root, int index, int nodesCount) 
{
    if (!root) return true;

    if (index >= nodesCount) 
    				return false;

    // Check heap property
    if ((root->left && root->left->data > root->data) ||
        (root->right && root->right->data > root->data))
        return false;

    return solution(root->left, 2*index+1, nodesCount) &&
           solution(root->right, 2*index+2, nodesCount);
}

int main() {
    // Binary Tree
    //        90
    //       /  \
    //      40    30
    //     / \    / \
    //    25  20 15   21
    //   /  \
    //  10    5
    Node *root = new Node(90);
    root->left = new Node(40);
    root->right = new Node(30);
    root->left->left = new Node(25);
    root->left->right = new Node(20);
    root->right->left = new Node(15);
    root->right->right = new Node(21);
    root->left->left->left = new Node(10);
    root->left->left->right = new Node(5);

    if (solution(root, 0, 9))
        cout << "true" << endl;
    else
        cout << "false" << endl;

    return 0;
}

Output

true