   # How to check if a given Binary Tree is Heap?

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). posted Nov 3, 2015

+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

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
Similar Questions
+1 vote

For example

Input : Binary Tree

``````               A
/    \
B        E
/   \       \
C     D       B
/  \
C    D
``````

Output : Yes