Given level order traversal of a Binary Tree, check if the Tree is a Min-Heap

Introduction

In this blog, we will discuss the approach to checking if the given Tree is a min-heap or not where we will be given the level order traversal of the Tree. Before jumping on the approach to the problem, let us first understand the problem.

Problem Statement

Given a binary tree, we need to check whether the Tree satisfies the conditions of a min-heap. Note that we will be given the level order traversal of the binary Tree.

Sample Example

Input: 

Output: True

Since for every node(parent), the value of its child is greater than the parent. Therefore it is a min-heap.

Input: 

Output: False

Since for the root node, the value of its child is smaller than that of its parent. Therefore it is not a min-heap.

Approach

This approach will check for every parent node whether its left and right child value are greater as compared to the parent value.

Algorithm

Step 1: Make a traversal for every parent node.

Step 2: For every parent node, first check whether its left subtree value is greater than the value of the parent. If it fails, return false. Otherwise,

Step 3: If the right child exists, check whether the value of the child is greater than that of the parent. If not, return false. Otherwise,

Step 4: Once checked for every node, return true.

Implementation

#include <bits/stdc++.h>
using namespace std;
//function to check if the tree is a min-heap or not
bool checkIfMinHeap(int level[],int size){
    //traversal of parent nodes where first parent node will be level[size/2-1]
    for(int i = (size/2-1);i>=0;i--){
        //checking for left child
        if(level[i] > level[2*i+1])
        return false;
        //checking for right child
        if(2*i + 2 < size){
            if(level[i] > level[2*i+2])
            return false;
        }
    }
    return true;
}
//Main function
int main(){
    int level[] = {5,8,7,11,14};
    int size = sizeof(level)/sizeof(level[0]);
    //calling the function to check for min-heap
    if(checkIfMinHeap(level,size))
    cout<<"True"<<endl;
    else
    cout<<"false"<<endl;
    return 0;
}

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

Run Code

Output:

 True

Complexity Analysis

Time complexity: O(n)

Since it only takes one traversal, which is of order n, therefore the time complexity of the approach is O(n).

Space complexity: O(1)

As no extra space is required apart from the given array, therefore space complexity of the approach is of the order O(1).\

Check out this problem - Diameter Of Binary Tree