Heap: Given level order traversal of Binary Tree, check if the tree is Min Heap

Problem Statement:

You are given level order of the Complete Binary Tree.

Check if the Binary Tree is a valid Min Heap

Example:

Input: arr[] = [3, 5, 9, 6, 8, 20, 10]

Solution Explanation:

For Min Heap, parent is smaller then its children.

For every parent, left child can be got by 2*i + 1.

For every parent, right child can be got by 2*i + 2.

check if it satisfies the condition and return the result

Code Solution

#include <iostream>
#include <vector>
using namespace std;

bool solution(vector<int> arr) 
{   
    int n = arr.size();

    //start from the last non leaf node
    // check if each parent node is smaller than its children
    for (int i = (n / 2 - 1); i >= 0; i--) 
    {
        if (arr[i] > arr[2 * i + 1])
            return false;

        if (2 * i + 2 < n && arr[i] > arr[2 * i + 2])
            return false;
    }
    return true;
}

int main() 
{
    vector<int> arr = {3, 5, 9, 6, 8, 20, 10};

    if (solution(arr))
    	cout<< "True"<<endl;
    else
    	cout<< "False"<<endl;
    return 0;
}

Output

True