Check if a Given Array Represents a Binary Heap

Approach

The approach to the given problem is quite an interesting one. We compare each root node with its descendants. If each root node is greater than its children nodes, then the tree is a max-heap, and the given array represents a max-heap.

Algorithm

1. Pass the array to a function that can compare a root node to its children nodes.

2. If indexing starts with 0, the last internal node is found at index (n-2)/2, as if a tree is stored in an array, the value at (n-2)/2th node is the last internal node, where n is the length of the array. It becomes the base case that will return true.

3. The defined function will check recursively if the parent node is greater than the children node.

4.  If the parent node is greater than the children node's function will return true. Otherwise, it will return false.

5.  The function will finally return the boolean value, which will then be printed.

Implementation

#include <limits.h>
#include <stdio.h>


// Function to recursively compare parent and children nodes
bool heapChecker(int nums[], int i, int n)
{
    // Base case
    if (i >= (n - 1) / 2)
        return true;

    // If an internal node and is larger than its children,
    // and same is recursively true for the children
    if (nums[i] >= nums[2 * i + 1] && nums[i] >= nums[2 * i + 2] &&
        heapChecker(nums, 2 * i + 1, n) && heapChecker(nums, 2 * i + 2, n))
        return true;

    return false;
}


// Driver program
int main()
{
    int nums[] = {80, 13, 9, 5, 11, 1};
    int n = sizeof(nums) / sizeof(int) - 1;
    if (heapChecker(nums, 0, n))
    {
        printf("Yes");
    }
    else
    {
        printf("No");
    }
    
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Yes

Time Complexity

The Time Complexity of the defined solution is O(n), where n is the number of elements in the given array. It is because we traverse the array one time to compare parent nodes to children nodes of the tree.

Space Complexity

The program's auxiliary space is O(1) because no additional data structure is involved.
Check out this problem - Largest BST In Binary Tree

Frequently Asked Questions

What is BFS?

Breadth-first search is a graph traversal technique that begins at the root node and searches all adjacent nodes. Then it chooses the closest node and investigates all undiscovered nodes.

Explain Max-heap?

A max-heap can be defined as a complete binary tree in which each internal node's value is larger than or equal to the values of that node's children.

What is a deque data structure?

A Deque is a queue that allows elements to be added and deleted from either the front or the rear.

Conclusion

In this blog, we discussed a coding problem where we checked if a given array represents a binary heap or not using a recursive approach. We discussed the time and space complexity of the approach as well.

Cheers, you have reached the end. Hope you liked the blog and it has added some knowledge to your life. Please look at these similar topics to learn more: Implementation of Heap, Binary Heap, Build Heap, Min Heap.

Recommended problems -

• Max circular subarray sum
• Shortest subarray with sum at least k
• Maximum sum subarray of size k
• Subarray sums divisible by k

Refer to our Coding Ninjas Studio Guided Path to learn Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, and even more! If you want to test your coding skills, check out the mock test series and participate in the contests hosted by Coding Ninjas Studio! But say you're just starting and want to learn about questions posed by tech titans like Amazon, Microsoft, Uber, and so on. In such a case, for placement preparations, you can also look at the problems, interview experiences, and interview bundle.

You should also consider our premium courses to offer your career advantage over others!

Please upvote our blogs if you find them useful and exciting!

Happy Coding!