top button
Flag Notify
    Connect to us
      Facebook Login
      Site Registration

Facebook Login
Site Registration

How to check if a given Binary Tree is Heap?

+2 votes
577 views

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?

posted Nov 3, 2015 by anonymous

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

2 Answers

+1 vote

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 Nov 4, 2015 by Salil Agrawal
0 votes

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.

answer Nov 3, 2015 by Amit Kumar Pandey
Contact Us
+91 9880187415
sales@queryhome.net
support@queryhome.net
#280, 3rd floor, 5th Main
6th Sector, HSR Layout
Bangalore-560102
Karnataka INDIA.
QUERY HOME
...