Given a binary tree. The task is to check whether the given tree follows the max heap property or not.
Note: Properties of a tree to be a max heap - Completeness and Value of node greater than or equal to its child.
Example 1:
Input:
      5
    /  \
   2    3
Output: 1
Explanation: The given tree follows max-heap property since 5,
is root and it is greater than both its children.
Example 2:
Input:
       10
     /   \
    20   30 
  /   \
 40   60
Output: 0
Your Task:
You don't need to read input or print anything. Your task is to complete the function isHeap() which takes the root of Binary Tree as parameter returns True if the given binary tree is a heap else returns False.
Expected Time Complexity: O(N)
Expected Space Complexity: O(N)
Constraints:
1 ≤ Number of nodes ≤ 100
1 ≤ Data of a node ≤ 1000

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Range queries

Starter code: #User Template for python3



'''

class Node:

    def __init__(self,val):

        self.data = val

        self.left = None

        self.right = None

'''



class Solution:

    #Your Function Should return True/False

    def isHeap(self, root):

        #Code Here

Solutions:
def countnodes(root):
	if not root:
		return 0
	ans = 1 + countnodes(root.left) + countnodes(root.right)
	return ans

def isCBT(root, index, count):
	if not root:
		return True
	if index >= count:
		return False
	left = isCBT(root.left, 2 * index + 1, count)
	right = isCBT(root.right, 2 * index + 2, count)
	return left and right

def maxorder(root):
	if root.left is None and root.right is None:
		return True
	if root.right is None:
		return root.data > root.left.data
	left = maxorder(root.left)
	right = maxorder(root.right)
	return left and right and (root.data > root.left.data) and (root.data > root.right.data)

class Solution:

	def isHeap(self, root):
		index = 0
		totalcount = countnodes(root)
		if isCBT(root, index, totalcount) and maxorder(root):
			return True
		else:
			return False


class Solution:

	def isHeap(self, root):
		queue = [root]
		flag = 0
		while queue:
			node = queue.pop(0)
			if node.left:
				queue.append(node.left)
				if flag == 1 or node.left.data > node.data:
					return False
			else:
				flag = 1
			if node.right:
				queue.append(node.right)
				if flag == 1 or node.right.data > node.data:
					return False
			else:
				flag = 1
		return True