How to check if a given Binary Tree is Heap?

Question

Binary tree need to fulfill following two conditions for being a heap –
* It should be a complete tree (i.e. all levels except last should be full).
* Every node’s value should be greater than or equal to its child node (considering max-heap).

C/C++ code would be helpful?

Answer 1

Few points to consider -
- One check if binary tree is complete or not which mean every Node can have 2 children, 0 child (last level nodes) or 1 child (there can be at most one such node).
- knowing the condition one is true then check if it is heap i.e. every node should be greater then its child nodes.

See the following code -

bool isComplete(struct Node* root, unsigned int index, unsigned int number_nodes)
{
    if (root == NULL)
        return (true);

    // If index assigned to current node is more than number of nodes in tree, then tree is not complete
    if (index >= number_nodes)
        return (false);

    return (isComplete(root->lnode, 2*index + 1, number_nodes) &&
            isComplete(root->rnode, 2*index + 2, number_nodes));
}


// This Function checks the heap property in the tree.
bool isHeapUtil(struct Node* root)
{
    //  Base case : single node satisfies property
    if (root->lnode == NULL && root->rnode == NULL)
        return (true);

    //  node will be in second last level
    if (root->rnode == NULL)
    {
        return (root->key >= root->lnode->key);
    }
    else
    {
        if (root->key >= root->lnode->key && root->key >= root->rnode->key)
            return ((isHeapUtil(root->lnode)) && (isHeapUtil(root->rnode)));
        else
            return (false);
    }
}

//  Function to check binary tree is a Heap or Not.
bool isHeap(struct Node* root)
{
    unsigned int node_count = countNodes(root);
    unsigned int index = 0;

    if (isComplete(root, index, node_count) && isHeapUtil(root))
        return true;
    return false;
}

Answer 2

Given a binary tree we need to check it has heap property or not, Binary tree need to fulfill following two conditions for being a heap –

1. It should be a complete tree (i.e. all levels except last should be full).
2. Every node’s value should be greater than or equal to its child node (considering max-heap).

We strongly recommend you to minimize your browser and try this yourself first.

We check each of the above condition separately, for checking completeness isComplete and for checking heap isHeapUtil function are written.
Detail about isComplete function can be found here.

isHeapUtil function is written considering following things –

Every Node can have 2 children, 0 child (last level nodes) or 1 child (there can be at most one such node).
If Node has No child then it’s a leaf node and return true (Base case)
If Node has one child (it must be left child because it is a complete tree) then we need to compare this node with its single child only.
If Node has both child then check heap property at Node at recur for both subtrees.
Complete code.