Given level order traversal of a Binary Tree, check if the Tree is a Min-Heap
Last Updated :
26 Dec, 2022
Given the level order traversal of a Complete Binary Tree, determine whether the Binary Tree is a valid Min-Heap
Examples:
Input : level = [10, 15, 14, 25, 30]
Output : True
The tree of the given level order traversal is
10
/ \
15 14
/ \
25 30
We see that each parent has a value less than
its child, and hence satisfies the min-heap
property
Input : level = [30, 56, 22, 49, 30, 51, 2, 67]
Output : False
The tree of the given level order traversal is
30
/ \
56 22
/ \ / \
49 30 51 2
/
67
We observe that at level 0, 30 > 22, and hence
min-heap property is not satisfied
We need to check whether each non-leaf node (parent) satisfies the heap property. For this, we check whether each parent (at index i) is smaller than its children (at indices 2*i+1 and 2*i+2, if the parent has two children). If only one child, we only check the parent against index 2*i+1.
C++
#include <bits/stdc++.h>
using namespace std;
bool isMinHeap(int level[], int n)
{
for (int i=(n/2-1) ; i>=0 ; i--)
{
if (level[i] > level[2 * i + 1])
return false;
if (2*i + 2 < n)
{
if (level[i] > level[2 * i + 2])
return false;
}
}
return true;
}
int main()
{
int level[] = {10, 15, 14, 25, 30};
int n = sizeof(level)/sizeof(level[0]);
if (isMinHeap(level, n))
cout << "True";
else
cout << "False";
return 0;
}
|
Java
import java.io.*;
import java.util.*;
public class detheap
{
static boolean isMinHeap(int []level)
{
int n = level.length - 1;
for (int i=(n/2-1) ; i>=0 ; i--)
{
if (level[i] > level[2 * i + 1])
return false;
if (2*i + 2 < n)
{
if (level[i] > level[2 * i + 2])
return false;
}
}
return true;
}
public static void main(String[] args)
throws IOException
{
int[] level = new int[]{10, 15, 14, 25, 30};
if (isMinHeap(level))
System.out.println("True");
else
System.out.println("False");
}
}
|
Python3
def isMinHeap(level, n):
for i in range(int(n / 2) - 1, -1, -1):
if level[i] > level[2 * i + 1]:
return False
if 2 * i + 2 < n:
if level[i] > level[2 * i + 2]:
return False
return True
if __name__ == '__main__':
level = [10, 15, 14, 25, 30]
n = len(level)
if isMinHeap(level, n):
print("True")
else:
print("False")
|
C#
using System;
class GFG
{
public static bool isMinHeap(int[] level)
{
int n = level.Length - 1;
for (int i = (n / 2 - 1) ; i >= 0 ; i--)
{
if (level[i] > level[2 * i + 1])
{
return false;
}
if (2 * i + 2 < n)
{
if (level[i] > level[2 * i + 2])
{
return false;
}
}
}
return true;
}
public static void Main(string[] args)
{
int[] level = new int[]{10, 15, 14, 25, 30};
if (isMinHeap(level))
{
Console.WriteLine("True");
}
else
{
Console.WriteLine("False");
}
}
}
|
PHP
<?php
function isMinHeap($level, $n)
{
for ($i = ($n / 2 - 1); $i >= 0; $i--)
{
if ($level[$i] > $level[2 * $i + 1])
return false;
if (2 * $i + 2 < $n)
{
if ($level[$i] > $level[2 * $i + 2])
return false;
}
}
return true;
}
$level = array(10, 15, 14, 25, 30);
$n = sizeof($level);
if (isMinHeap($level, $n))
echo "True";
else
echo "False";
|
Javascript
<script>
function isMinHeap(level)
{
var n = level.length - 1;
for(var i = (n / 2 - 1) ; i >= 0 ; i--)
{
if (level[i] > level[2 * i + 1])
{
return false;
}
if (2 * i + 2 < n)
{
if (level[i] > level[2 * i + 2])
{
return false;
}
}
}
return true;
}
var level = [10, 15, 14, 25, 30];
if (isMinHeap(level))
{
document.write("True");
}
else
{
document.write("False");
}
</script>
|
Time Complexity: O(n)
Auxiliary Space: O(1)
Please Login to comment...