Check if a given Binary Tree is Heap - GeeksforGeeks

Check if a given Binary Tree is Heap - GeeksforGeeks
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 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.
Check whether a given Binary Tree is Complete or not
1. Level Order Traversal
2.

1. Calculate the number of nodes (count) in the binary tree.
2. Start recursion of the binary tree from the root node of the binary tree with index (i) being set as 0 and the number of nodes in the binary (count).
3. If the current node under examination is NULL, then the tree is a complete binary tree. Return true.
4. If index (i) of the current node is greater than or equal to the number of nodes in the binary tree (count) i.e. (i>= count), then the tree is not a complete binary. Return false.
5. Recursively check the left and right sub-trees of the binary tree for same condition. For the left sub-tree use the index as (2*i + 1) while for the right sub-tree use the index as (2*i + 2).

/* This function counts the number of nodes in a binary tree */

unsigned int countNodes(struct Node* root)

{

    if (root == NULL)

        return (0);

    return (1 + countNodes(root->left) + countNodes(root->right));

}

 

/* This function checks if the binary tree is complete or not */

bool isCompleteUtil (struct Node* root, unsigned int index,

                     unsigned int number_nodes)

{

    // An empty tree is complete

    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);

 

    // Recur for left and right subtrees

    return (isCompleteUtil(root->left, 2*index + 1, number_nodes) &&

            isCompleteUtil(root->right, 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->left == NULL && root->right == NULL)

        return (true);

 

    //  node will be in second last level

    if (root->right == NULL)

    {

        //  check heap property at Node

        //  No recursive call , because no need to check last level

        return (root->key >= root->left->key);

    }

    else

    {

        //  Check heap property at Node and

        //  Recursive check heap property at left and right subtree

        if (root->key >= root->left->key &&

            root->key >= root->right->key)

            return ((isHeapUtil(root->left)) &&

                    (isHeapUtil(root->right)));

        else

            return (false);

    }

}

 

//  Function to check binary tree is a Heap or Not.

bool isHeap(struct Node* root)

{

    // These two are used in isCompleteUtil()

    unsigned int node_count = countNodes(root);

    unsigned int index = 0;

 

    if (isCompleteUtil(root, index, node_count) && isHeapUtil(root))

        return true;

    return false;

}

Read full article from Check if a given Binary Tree is Heap - GeeksforGeeks