# 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
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

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 ` `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

 `= 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 `

Output:

```True
```

These algorithms run with worse case O(n) complexity

## tags:

Heap Tree tree-level-order Tree Heap