Given level order traversal of a Binary Tree, check if the Tree is a Min-Heap
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++
// C++ program to check if a given tree is // Binary Heap or not #include <bits/stdc++.h> using namespace std; // Returns true if given level order traversal // is Min Heap. bool isMinHeap( int level[], int n) { // First non leaf node is at index (n/2-1). // Check whether each parent is greater than child for ( int i=(n/2-1) ; i>=0 ; i--) { // Left child will be at index 2*i+1 // Right child will be at index 2*i+2 if (level[i] > level[2 * i + 1]) return false ; if (2*i + 2 < n) { // If parent is greater than right child if (level[i] > level[2 * i + 2]) return false ; } } return true ; } // Driver code 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
// Java program to check if a given tree is // Binary Heap or not import java.io.*; import java.util.*; public class detheap { // Returns true if given level order traversal // is Min Heap. static boolean isMinHeap( int []level) { int n = level.length - 1 ; // First non leaf node is at index (n/2-1). // Check whether each parent is greater than child for ( int i=(n/ 2 - 1 ) ; i>= 0 ; i--) { // Left child will be at index 2*i+1 // Right child will be at index 2*i+2 if (level[i] > level[ 2 * i + 1 ]) return false ; if ( 2 *i + 2 < n) { // If parent is greater than right child if (level[i] > level[ 2 * i + 2 ]) return false ; } } return true ; } // Driver code public static void main(String[] args) throws IOException { // Level order traversal int [] level = new int []{ 10 , 15 , 14 , 25 , 30 }; if (isMinHeap(level)) System.out.println( "True" ); else System.out.println( "False" ); } } |
Python3
# Python3 program to check if a given # tree is Binary Heap or not # Returns true if given level order # traversal is Min Heap. def isMinHeap(level, n): # First non leaf node is at index # (n/2-1). Check whether each parent # is greater than child for i in range ( int (n / 2 ) - 1 , - 1 , - 1 ): # Left child will be at index 2*i+1 # Right child will be at index 2*i+2 if level[i] > level[ 2 * i + 1 ]: return False if 2 * i + 2 < n: # If parent is greater than right child if level[i] > level[ 2 * i + 2 ]: return False return True # Driver code if __name__ = = '__main__' : level = [ 10 , 15 , 14 , 25 , 30 ] n = len (level) if isMinHeap(level, n): print ( "True" ) else : print ( "False" ) # This code is contributed by PranchalK |
C#
// C# program to check if a given tree // is Binary Heap or not using System; class GFG { // Returns true if given level // order traversal is Min Heap. public static bool isMinHeap( int [] level) { int n = level.Length - 1; // First non leaf node is at // index (n/2-1). Check whether // each parent is greater than child for ( int i = (n / 2 - 1) ; i >= 0 ; i--) { // Left child will be at index 2*i+1 // Right child will be at index 2*i+2 if (level[i] > level[2 * i + 1]) { return false ; } if (2 * i + 2 < n) { // If parent is greater than right child if (level[i] > level[2 * i + 2]) { return false ; } } } return true ; } // Driver code public static void Main( string [] args) { // Level order traversal int [] level = new int []{10, 15, 14, 25, 30}; if (isMinHeap(level)) { Console.WriteLine( "True" ); } else { Console.WriteLine( "False" ); } } } // This code is contributed by Shrikant13 |
PHP
<?php // PHP program to check if a given tree // is Binary Heap or not // Returns true if given level order // traversal is Min Heap. function isMinHeap( $level , $n ) { // First non leaf node is at index // (n/2-1). Check whether each parent // is greater than child for ( $i = ( $n / 2 - 1); $i >= 0; $i --) { // Left child will be at index 2*i+1 // Right child will be at index 2*i+2 if ( $level [ $i ] > $level [2 * $i + 1]) return false; if (2 * $i + 2 < $n ) { // If parent is greater than right child if ( $level [ $i ] > $level [2 * $i + 2]) return false; } } return true; } // Driver code $level = array (10, 15, 14, 25, 30); $n = sizeof( $level ); if (isMinHeap( $level , $n )) echo "True" ; else echo "False" ; // This code is contributed // by Akanksha Rai |
Javascript
<script> // JavaScript program to check if a given tree // is Binary Heap or not // Returns true if given level // order traversal is Min Heap. function isMinHeap(level) { var n = level.length - 1; // First non leaf node is at // index (n/2-1). Check whether // each parent is greater than child for ( var i = (n / 2 - 1) ; i >= 0 ; i--) { // Left child will be at index 2*i+1 // Right child will be at index 2*i+2 if (level[i] > level[2 * i + 1]) { return false ; } if (2 * i + 2 < n) { // If parent is greater than right child if (level[i] > level[2 * i + 2]) { return false ; } } } return true ; } // Driver code // Level order traversal var level = [10, 15, 14, 25, 30]; if (isMinHeap(level)) { document.write( "True" ); } else { document.write( "False" ); } </script> |
Output
True
Time Complexity: O(n)
Auxiliary Space: O(1)
Contact Us