Given a Binary Search Tree. Convert a given BST into a Special Max Heap with the condition that all the values in the left subtree of a node should be less than all the values in the right subtree of the node. This condition is applied on all the nodes in the so converted Max Heap.
Example 1:
Input :
                 4
               /   \
              2     6
            /  \   /  \
           1   3  5    7  
Output : 1 2 3 4 5 6 7 
Exaplanation :
               7
             /   \
            3     6
          /   \  /   \
         1    2 4     5
The given BST has been transformed into a
Max Heap and it's postorder traversal is
1 2 3 4 5 6 7.
Your task :
You don't need to read input or print anything. Your task is to complete the function convertToMaxHeapUtil() which takes the root of the tree as input and converts the BST to max heap. 
Note : The driver code prints the postorder traversal of the converted BST.
 
Expected Time Complexity : O(n)
Expected Auxiliary Space : O(n)
 
Constraints :
1 ≤ n ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Range queries

Starter code: #User function Template for python3



'''

# Tree Node

class Node:

    def __init__(self, val):

        self.right = None

        self.data = val

        self.left = None

        

'''



class Solution:

    def convertToMaxHeapUtil(self, root):

        #code here

Solutions:
class Solution:

	def inorder(self, root, lis):
		if root == None:
			return
		self.inorder(root.left, lis)
		lis.append(root.data)
		self.inorder(root.right, lis)

	def solve(self, root, lis):
		if root == None:
			return
		self.solve(root.left, lis)
		self.solve(root.right, lis)
		root.data = lis.pop()

	def convertToMaxHeapUtil(self, root):
		lis = []
		self.inorder(root, lis)
		lis = lis[::-1]
		self.solve(root, lis)
		return root


class Solution:

	def convertToMaxHeapUtil(self, root):
		lis = []
		self.inorder(root, lis)
		lis = lis[::-1]
		self.postorder(root, lis)
		return root

	def inorder(self, rt, li):
		if rt is None:
			return
		self.inorder(rt.left, li)
		li.append(rt.data)
		self.inorder(rt.right, li)

	def postorder(self, rt, li):
		if rt is None:
			return
		self.postorder(rt.left, li)
		self.postorder(rt.right, li)
		rt.data = li.pop()


class Solution:

	def Inorder(self, root, arr):
		if root == None:
			return None
		self.Inorder(root.left, arr)
		arr.append(root.data)
		self.Inorder(root.right, arr)

	def post(self, root, arr):
		if root == None:
			return None
		self.post(root.left, arr)
		self.post(root.right, arr)
		root.data = arr[-1]
		arr.pop(-1)

	def convertToMaxHeapUtil(self, root):
		arr = []
		self.Inorder(root, arr)
		arr.reverse()
		self.post(root, arr)


class Solution:

	def inorder(self, root, c):
		if root:
			self.inorder(root.left, c)
			c.append(root.data)
			self.inorder(root.right, c)

	def postorder(self, root, c):
		if root:
			self.postorder(root.left, c)
			self.postorder(root.right, c)
			root.data = c[self.i]
			self.i += 1

	def convertToMaxHeapUtil(self, root):
		c = []
		p = []
		self.i = 0
		self.inorder(root, c)
		self.postorder(root, c)
		return c


class Solution:

	def preorder(self, root, arr):
		if root == None:
			return
		self.preorder(root.left, arr)
		arr.append(root.data)
		self.preorder(root.right, arr)

	def convert(self, root, arr):
		if root == None:
			return
		root.left = self.convert(root.left, arr)
		root.right = self.convert(root.right, arr)
		root.data = arr[self.i]
		self.i += 1
		return root

	def convertToMaxHeapUtil(self, root):
		arr = []
		self.preorder(root, arr)
		self.i = 0
		root = self.convert(root, arr)
		return root


class Solution:

	def convertToMaxHeapUtil(self, root):
		arr = []

		def inorder(root):
			if root == None:
				return
			inorder(root.left)
			arr.append(root.data)
			inorder(root.right)
		self.i = 0

		def postorder(root):
			if root == None:
				return
			postorder(root.left)
			postorder(root.right)
			root.data = arr[self.i]
			self.i += 1
		inorder(root)
		postorder(root)
		return root


import heapq

class Solution:

	def convertToMaxHeapUtil(self, root):
		stk = []

		def inorder(root):
			if not root:
				return
			inorder(root.left)
			stk.append(root.data)
			inorder(root.right)
		inorder(root)
		stk.reverse()

		def postorder(root):
			if not root:
				return
			postorder(root.left)
			postorder(root.right)
			root.data = stk.pop()
		postorder(root)


class Solution:

	def convertToMaxHeapUtil(self, root):
		l = []

		def dfs(root, l):
			if root == None:
				return
			dfs(root.left, l)
			l.append(root.data)
			dfs(root.right, l)
		i = [-1]
		dfs(root, l)

		def maxh(root, i):
			if root == None:
				return
			maxh(root.left, i)
			maxh(root.right, i)
			i[0] = i[0] + 1
			root.data = l[i[0]]
		maxh(root, i)
		return root


class Solution:

	def convertToMaxHeapUtil(self, root):
		self.i = 0

		def manu(root, a):
			if root is None:
				return
			manu(root.left, a)
			a.append(root.data)
			manu(root.right, a)
		a = []
		manu(root, a)

		def postorder(root, i, a):
			if root is None:
				return
			root.left = postorder(root.left, i, a)
			root.right = postorder(root.right, i, a)
			root.data = a[i[0]]
			i[0] += 1
			return root
		postorder(root, [0], a)


class Solution:

	def heapify(self, root, temp):
		if root is None:
			return
		if root.left is None and root.right is None:
			return
		largest = root
		if root.left:
			if root.data < root.left.data:
				largest = root.left
		if root.right:
			if root.data < root.right.data:
				largest = root.right
		if largest != root:
			(root, largest) = (largest, root)
			self.heapify(largest, root)
		else:
			self.heapify(root, largest)

	def ino_post(self, root, s):
		if root is None:
			return
		if root:
			self.ino_post(root.left, s)
			s.append(root.data)
			self.ino_post(root.right, s)
			root.data = s[self.cnt]
			self.cnt += 1

	def convertToMaxHeapUtil(self, root):
		s = []
		self.cnt = 0
		self.ino_post(root, s)


def inOrder(root):
	if root == None:
		return []
	return inOrder(root.left) + [root.data] + inOrder(root.right)

def convert(arr, pos, n, k):
	if k >= n:
		return (pos, None)
	nptr = Node(arr[pos])
	(pos, nptr.right) = convert(arr, pos - 1, n, 2 * k + 2)
	(pos, nptr.left) = convert(arr, pos, n, 2 * k + 1)
	return (pos, nptr)

class Solution:

	def convertToMaxHeapUtil(self, root):
		arr = inOrder(root)
		n = len(arr)
		nptr = convert(arr, n - 1, n, 0)[1]
		root.data = nptr.data
		(root.left, root.right) = (nptr.left, nptr.right)


class Solution:

	def __init__(self):
		self.A = []
		self.ind = 0

	def buildTree(self, root, A, ind):
		if root == None:
			return
		self.buildTree(root.left, A, ind)
		self.buildTree(root.right, A, ind)
		root.data = self.A[self.ind]
		self.ind += 1

	def inorder(self, root, A):
		if root == None:
			return
		self.inorder(root.left, A)
		A.append(root.data)
		self.inorder(root.right, A)

	def convertToMaxHeapUtil(self, root):
		self.inorder(root, self.A)
		self.buildTree(root, self.A, self.ind)


class Solution:

	def dfs(self, root, arr):
		if not root:
			return
		self.dfs(root.left, arr)
		arr.append(root.data)
		self.dfs(root.right, arr)

	def convert(self, root, arr):
		if root == None:
			return
		root.left = self.convert(root.left, arr)
		root.right = self.convert(root.right, arr)
		root.data = arr[self.i]
		self.i += 1
		return root

	def convertToMaxHeapUtil(self, root):
		self.i = 0
		arr = []
		self.dfs(root, arr)
		res = self.convert(root, arr)
		return res


class Solution:

	def convertToMaxHeapUtil(self, root):
		arr = self.getItems(root)
		stack = [root]
		while stack:
			head = stack.pop()
			if head == None:
				continue
			head.data = arr.pop()
			stack.append(head.left)
			stack.append(head.right)
		return

	def getItems(self, root):
		if root is None:
			return []
		output = []
		output += self.getItems(root.left)
		output += [root.data]
		output += self.getItems(root.right)
		return output


class Solution:

	def inorder(self, root, l):
		if not root:
			return
		self.inorder(root.left, l)
		l.append(root.data)
		self.inorder(root.right, l)

	def fill(self, root, l, i):
		if not root:
			return
		self.fill(root.left, l, i)
		self.fill(root.right, l, i)
		root.data = l[i[0]]
		i[0] += 1

	def convertToMaxHeapUtil(self, root):
		l = []
		self.inorder(root, l)
		i = [0]
		self.fill(root, l, i)
		return root


class Solution:

	def convertToMaxHeapUtil(self, root):
		arr = []

		def inorder(node):
			if not node:
				return None
			inorder(node.left)
			arr.append(node.data)
			inorder(node.right)

		def postOrder(node):
			if not node:
				return None
			postOrder(node.left)
			postOrder(node.right)
			node.data = arr.pop()
		inorder(root)
		arr.reverse()
		postOrder(root)
		return root


class Solution:

	def getArr(self, root, ls):
		if not root:
			return
		self.getArr(root.left, ls)
		ls.append(root.data)
		self.getArr(root.right, ls)

	def generateTree(self, ls, idx, root):
		if not root or idx[0] == len(ls):
			return
		self.generateTree(ls, idx, root.left)
		self.generateTree(ls, idx, root.right)
		idx[0] += 1
		root.data = ls[idx[0]]

	def convertToMaxHeapUtil(self, root):
		ls = []
		self.getArr(root, ls)
		n = len(s)
		i = [-1]
		self.generateTree(ls, i, root)


class Solution:

	def inorder(self, root, arr):
		if not root:
			return
		self.inorder(root.left, arr)
		arr.append(root.data)
		self.inorder(root.right, arr)

	def solve(self, root, arr, i):
		if not root:
			return
		self.solve(root.left, arr, i)
		self.solve(root.right, arr, i)
		root.data = arr[i[0]]
		i[0] += 1

	def convertToMaxHeapUtil(self, root):
		arr = []
		self.inorder(root, arr)
		self.solve(root, arr, [0])
		return root


def innorder(root):
	if not root:
		return []
	return innorder(root.left) + [root.data] + innorder(root.right)

def BSTToMaxHeap(root, arr):
	global i
	if root == None:
		return None
	root.left = BSTToMaxHeap(root.left, arr)
	root.right = BSTToMaxHeap(root.right, arr)
	root.data = arr[i]
	i = i + 1
	return root

class Solution:

	def convertToMaxHeapUtil(self, root):
		arr = innorder(root)
		global i
		i = 0
		return BSTToMaxHeap(root, arr)


class Solution:

	def convertToMaxHeapUtil(self, root):

		def inorderTraversal(root, arr):
			if root == None:
				return
			inorderTraversal(root.left, arr)
			arr.append(root.data)
			inorderTraversal(root.right, arr)

		def BSTtoMaxHeap(root, arr, i):
			if root == None:
				return
			BSTtoMaxHeap(root.left, arr, i)
			BSTtoMaxHeap(root.right, arr, i)
			i[0] += 1
			root.data = arr[i[0]]
		arr = []
		i = [-1]
		inorderTraversal(root, arr)
		BSTtoMaxHeap(root, arr, i)


class Solution:

	def convertToMaxHeapUtil(self, root):
		st = deque()
		nodes = []
		current = root
		while current:
			if current.left:
				left = current.left
				while left.right and left.right != current:
					left = left.right
				if left.right == None:
					left.right = current
					current = current.left
				if left.right == current:
					left.right = None
					nodes.append(current.data)
					current = current.right
			else:
				nodes.append(current.data)
				current = current.right
		current = root
		i = 0
		while 1:
			while current:
				st.append(current)
				st.append(current)
				current = current.left
			if not st:
				break
			nd = st.pop()
			if st and st[-1] == nd:
				current = nd.right
			else:
				nd.data = nodes[i]
				i += 1


class Solution:

	def inOrder(self, root):
		cur = root
		stack = []
		ans = []
		while 1:
			if cur is not None:
				stack.append(cur)
				cur = cur.left
			elif stack:
				cur = stack.pop()
				ans.append(cur.data)
				cur = cur.right
			else:
				break
		return ans

	def BSTToMaxHeap(self, root, arr):
		if root == None:
			return None
		root.left = self.BSTToMaxHeap(root.left, arr)
		root.right = self.BSTToMaxHeap(root.right, arr)
		root.data = arr.pop()
		return root

	def convertToMaxHeapUtil(self, root):
		ans = self.inOrder(root)
		ans.reverse()
		return self.BSTToMaxHeap(root, ans)


class Solution:

	def convertToMaxHeapUtil(self, root):
		res = []

		def inorder(root):
			if not root:
				return
			inorder(root.left)
			res.append(root.data)
			inorder(root.right)
		i = [-1]

		def postorder(root, res, i):
			if not root:
				return
			postorder(root.left, res, i)
			postorder(root.right, res, i)
			i[0] += 1
			root.data = res[i[0]]
		inorder(root)
		postorder(root, res, i)


import heapq

class Solution:

	def __init__(self):
		self.count = 0

	def convertToMaxHeapUtil(self, root):
		ans = []

		def helper(root, ans):
			if root == None:
				return
			helper(root.left, ans)
			ans.append(root.data)
			helper(root.right, ans)

		def helper2(root, ans, t):
			if root == None:
				return
			helper2(root.left, ans, t)
			helper2(root.right, ans, t)
			root.data = ans[self.count]
			self.count += 1
		helper(root, ans)
		t = 0
		helper2(root, ans, t)
		return root


class Solution:

	def convertToMaxHeapUtil(self, root):

		def reverseInorder(root):
			if not root:
				return
			reverseInorder(root.right)
			arr.append(root.data)
			reverseInorder(root.left)

		def convertBSTToMaxHeap(root):
			nonlocal index
			if not root:
				return
			root.data = arr[index]
			index += 1
			convertBSTToMaxHeap(root.right)
			convertBSTToMaxHeap(root.left)
		arr = []
		index = 0
		reverseInorder(root)
		convertBSTToMaxHeap(root)


class Solution:

	def convertToMaxHeapUtil(self, root):
		global i
		i = 0
		arr = []

		def inOrder(root):
			if root == None:
				return arr
			inOrder(root.left)
			arr.append(root.data)
			inOrder(root.right)

		def bstToHeap(root):
			global i
			if root == None:
				return None
			root.left = bstToHeap(root.left)
			root.right = bstToHeap(root.right)
			root.data = arr[i]
			i += 1
			return root
		inOrder(root)
		root = bstToHeap(root)
		return root


class Solution:

	def convertToMaxHeapUtil(self, root):

		def inorder(root, l):
			if root:
				inorder(root.left, l)
				l.append(root.data)
				inorder(root.right, l)

		def order(root, l):
			if root:
				order(root.left, l)
				order(root.right, l)
				root.data = l[-1]
				l.pop(-1)
		l = []
		inorder(root, l)
		l = l[::-1]
		order(root, l)


class Solution:

	def convertToMaxHeapUtil(self, root):
		v = []

		def inorder(x):
			if x:
				inorder(x.left)
				v.append(x.data)
				inorder(x.right)

		def preorder(x):
			if x:
				preorder(x.left)
				preorder(x.right)
				x.data = v[i[0]]
				i[0] += 1
		inorder(root)
		i = [0]
		preorder(root)
		return root


class Solution:

	def inorder(self, root, res):
		if root is None:
			return
		self.inorder(root.left, res)
		res.append(root.data)
		self.inorder(root.right, res)

	def postorder(self, root, arr, idx):
		if root is None:
			return
		self.postorder(root.left, arr, idx)
		self.postorder(root.right, arr, idx)
		root.data = arr[idx[0]]
		idx[0] += 1

	def convertToMaxHeapUtil(self, root):
		res = []
		self.inorder(root, res)
		self.postorder(root, res, [0])


class Solution:

	def convertToMaxHeapUtil(self, root):
		In = []

		def inorder(root):
			if root == None:
				return
			inorder(root.left)
			In.append(root.data)
			inorder(root.right)
		inorder(root)
		global i
		i = 0

		def dfs(root):
			global i
			if root == None:
				return
			dfs(root.left)
			dfs(root.right)
			root.data = In[i]
			i += 1
		dfs(root)
		return root


class Solution:

	def convertToMaxHeapUtil(self, root):
		self.lst = []

		def dfs(root):
			if not root:
				return
			dfs(root.right)
			self.lst.append(root.data)
			dfs(root.left)
		dfs(root)
		self.i = 0

		def preorder(root):
			if not root:
				return
			root.data = self.lst[self.i]
			self.i += 1
			preorder(root.right)
			preorder(root.left)
		preorder(root)
		return root


class Solution:
	a = []
	i = 0

	def postt(self, r):
		if r == None:
			return
		self.postt(r.left)
		self.postt(r.right)
		r.data = Solution.a[Solution.i]
		Solution.i += 1

	def pret(self, r):
		if r == None:
			return
		self.pret(r.left)
		Solution.a.append(r.data)
		self.pret(r.right)

	def convertToMaxHeapUtil(self, root):
		Solution.a = []
		Solution.i = 0
		self.pret(root)
		self.postt(root)


class Solution:

	def __init__(self):
		self.res = []
		self.count = 0

	def inorder(self, temp):
		if temp is None:
			return
		self.inorder(temp.left)
		self.res.append(temp.data)
		self.inorder(temp.right)

	def postorder(self, temp):
		if temp is None:
			return
		self.postorder(temp.left)
		self.postorder(temp.right)
		temp.data = self.res[self.count]
		self.count += 1

	def convertToMaxHeapUtil(self, root):
		self.inorder(root)
		self.postorder(root)
		return root


class Solution:

	def convertToMaxHeapUtil(self, root):
		inord = []

		def inorder(root):
			nonlocal inord
			if not root:
				return
			else:
				inorder(root.left)
				inord.append(root.data)
				inorder(root.right)
		inorder(root)

		def postorder(root, arr):
			nonlocal inord
			if not root:
				return
			else:
				postorder(root.left, arr)
				postorder(root.right, arr)
				root.data = inord[arr[0]]
				arr[0] += 1
		postorder(root, [0])
		return root


import heapq

class Solution:

	def solve(self, root, pq):
		if root == None:
			return
		heapq.heappush(pq, root.data)
		self.solve(root.left, pq)
		self.solve(root.right, pq)

	def MaxHeap(self, root, pq):
		if root == None:
			return
		self.MaxHeap(root.left, pq)
		self.MaxHeap(root.right, pq)
		root.data = heapq.heappop(pq)

	def convertToMaxHeapUtil(self, root):
		pq = []
		self.solve(root, pq)
		self.MaxHeap(root, pq)


class Solution:

	def postorder(self, root, brr):
		if root == None:
			return
		self.postorder(root.left, brr)
		self.postorder(root.right, brr)
		brr.append(root)

	def inorder(self, root, arr):
		if root == None:
			return
		self.inorder(root.left, arr)
		arr.append(root.data)
		self.inorder(root.right, arr)

	def convertToMaxHeapUtil(self, root):
		arr = []
		brr = []
		curr = root
		self.inorder(curr, arr)
		curr = root
		self.postorder(curr, brr)
		for i in range(len(arr)):
			brr[i].data = arr[i]
		return root


def inorder(node, A):
	if node is None:
		return
	inorder(node.left, A)
	A.append(node.data)
	inorder(node.right, A)

def postorder(node, A, index):
	if node is None:
		return
	postorder(node.left, A, index)
	postorder(node.right, A, index)
	node.data = A[index[0]]
	index[0] += 1
	return

class Solution:

	def convertToMaxHeapUtil(self, root):
		index = [0]
		A = []
		inorder(root, A)
		postorder(root, A, index)
		return root


import collections

class Solution:

	def convertToMaxHeapUtil(self, root):
		temp = collections.deque()

		def inorder(root):
			if root == None:
				return
			inorder(root.left)
			temp.append(root.data)
			inorder(root.right)
		inorder(root)

		def maxHeap(root, temp):
			if root == None:
				return
			maxHeap(root.left, temp)
			maxHeap(root.right, temp)
			root.data = temp.popleft()
		maxHeap(root, temp)


class Solution:

	def inOrder(self, root, arr):
		if root is None:
			return arr
		self.inOrder(root.left, arr)
		arr.append(root.data)
		self.inOrder(root.right, arr)

	def postOrder(self, root, arr2, index):
		if root is None:
			return
		self.postOrder(root.left, arr2, index)
		self.postOrder(root.right, arr2, index)
		root.data = arr2[index[0]]
		index[0] += 1

	def convertToMaxHeapUtil(self, root):
		arr2 = []
		self.inOrder(root, arr2)
		index = [0] * 1
		self.postOrder(root, arr2, index)


class Solution:

	def inorder_trav(self, cur_node, inorder):
		if cur_node == None:
			return None
		self.inorder_trav(cur_node.left, inorder)
		inorder.append(cur_node.data)
		self.inorder_trav(cur_node.right, inorder)

	def convert_heap(self, inorder, l, r):
		if l > r:
			return
		mid = (l + r - 1) // 2
		root = Node(inorder[r])
		root.left = self.convert_heap(inorder, l, mid)
		root.right = self.convert_heap(inorder, mid + 1, r - 1)
		return root

	def convertToMaxHeapUtil(self, root):
		inorder = []
		self.inorder_trav(root, inorder)
		heap_root = self.convert_heap(inorder, 0, len(inorder) - 1)
		root.data = heap_root.data
		root.left = heap_root.left
		root.right = heap_root.right


class Solution:

	def convertToMaxHeapUtil(self, root):
		arr = []
		i = 0

		def inorder(root):
			if not root:
				return
			inorder(root.left)
			arr.append(root.data)
			inorder(root.right)

		def func(root):
			nonlocal i
			if not root:
				return None
			root.left = func(root.left)
			root.right = func(root.right)
			root.data = arr[i]
			i += 1
			return root
		inorder(root)
		return func(root)


class Solution:
	i = 0

	def convertToMaxHeapUtil(self, root):
		import heapq
		arr = []
		self.preorder(root, arr)
		arr[:] = arr[::-1]
		self.help(root, arr)
		return root

	def help(self, root, arr):
		if root == None:
			return
		self.help(root.left, arr)
		self.help(root.right, arr)
		root.data = arr[self.i]
		self.i += 1

	def preorder(self, root, arr):
		if root == None:
			return
		self.preorder(root.right, arr)
		arr.append(root.data)
		self.preorder(root.left, arr)


class Solution:

	def inorder(self, root, heap):
		if root:
			self.inorder(root.left, heap)
			heap.append(root.data)
			self.inorder(root.right, heap)

	def convert(self, root, heap):
		if root:
			self.convert(root.left, heap)
			self.convert(root.right, heap)
			root.data = heap.pop(0)

	def convertToMaxHeapUtil(self, root):
		import collections
		temp = collections.deque()

		def inorder(root):
			if root == None:
				return
			inorder(root.left)
			temp.append(root.data)
			inorder(root.right)
		inorder(root)

		def maxHeap(root, temp):
			if root == None:
				return
			maxHeap(root.left, temp)
			maxHeap(root.right, temp)
			root.data = temp.popleft()
		maxHeap(root, temp)


from heapq import *

class Solution:

	def convertToMaxHeapUtil(self, root):
		arr = []

		def Inorder(root):
			nonlocal arr
			if not root:
				return
			Inorder(root.left)
			arr.append(root.data)
			Inorder(root.right)
		idx = 0

		def Postorder(root):
			if not root:
				return
			nonlocal arr
			nonlocal idx
			Postorder(root.left)
			Postorder(root.right)
			root.data = arr[idx]
			idx += 1
		Inorder(root)
		Postorder(root)
		return root


class Solution:

	def convertToMaxHeapUtil(self, root):
		inOrd = []

		def inOrder(r):
			if not r:
				return
			inOrder(r.left)
			inOrd.append(r.data)
			inOrder(r.right)
		ind = [0]

		def postOrder(r):
			if not r:
				return
			postOrder(r.left)
			postOrder(r.right)
			r.data = inOrd[ind[0]]
			ind[0] += 1
		inOrder(root)
		postOrder(root)
		return root


from collections import deque

class Solution:

	def convertToMaxHeapUtil(self, root):
		values = []
		q = deque([root])
		while q:
			v = q.pop()
			values.append(v.data)
			if v.left != None:
				q.append(v.left)
			if v.right != None:
				q.append(v.right)
		values.sort(reverse=True)
		values = deque(values)

		def postorder(root):
			if root != None:
				root.data = values[0]
				values.popleft()
				postorder(root.right)
				postorder(root.left)
		postorder(root)
		return root


class Solution:

	def convertToMaxHeapUtil(self, roota):
		global root
		ret = self.inOrder(roota, [])
		root = self.buildHeap(ret)
		return root

	def buildHeap(self, ret):
		parent = ret[len(ret) - 1]
		left_index = len(ret) // 2 - 1
		left = ret[left_index]
		right = ret[len(ret) - 2]
		if parent is not None and left.data != parent.data:
			parent.left = left
			if parent.left.data != right.data:
				parent.right = right
			if parent.left is not None:
				parent.left.left = None
				parent.left.right = None
			if parent.right is not None:
				parent.right.left = None
				parent.right.right = None
		if left_index > 0:
			self.buildHeap(ret[:left_index + 1])
			self.buildHeap(ret[left_index + 1:len(ret) - 1])
		return parent

	def inOrder(self, root, ret):
		if root is None:
			return []
		self.inOrder(root.left, ret)
		if root is not None:
			ret.append(root)
		self.inOrder(root.right, ret)
		return ret


from heapq import *

class Solution:

	def convertToMaxHeapUtil(self, root):
		arr = []

		def Inorder(root):
			nonlocal arr
			if not root:
				return
			Inorder(root.left)
			arr.append(root.data)
			Inorder(root.right)
		idx = 0

		def Postorder(root):
			if not root:
				return
			nonlocal arr
			nonlocal idx
			Postorder(root.left)
			Postorder(root.right)
			root.data = arr[idx]
			idx += 1
		Inorder(root)
		Postorder(root)
		return root
		heap = []

		def fun(root):
			nonlocal heap
			if root:
				heappush(heap, -1 * root.data)
				fun(root.left)
				fun(root.right)
		fun(root)
		que = deque([root])
		while que:
			node = que.popleft()
			node.data = -1 * heappop(heap)
			if node.left:
				que.append(node.left)
			if node.right:
				que.append(node.right)
		return root


class Solution:
	(arr, index) = ([], 0)

	def inorder(self, root):
		if root != None:
			self.inorder(root.left)
			self.arr.append(root.data)
			self.inorder(root.right)

	def filltree(self, root):
		if root == None:
			return
		self.filltree(root.left)
		self.filltree(root.right)
		root.data = self.arr[self.index]
		self.index += 1

	def convertToMaxHeapUtil(self, root):
		(self.arr, self.index) = ([], 0)
		self.inorder(root)
		self.filltree(root)


def util(arr):
	if not arr:
		return None
	root = Node(arr[-1])
	arr = arr[:-1]
	n = len(arr)
	root.left = util(arr[:n // 2])
	root.right = util(arr[n // 2:])
	return root

def inorder(root, arr):
	if not root:
		return
	inorder(root.left, arr)
	arr.append(root.data)
	inorder(root.right, arr)

def preorder(root, arr):
	if not root:
		return
	arr.append(root.data)
	preorder(root.left, arr)
	preorder(root.right, arr)

class Solution:

	def convertToMaxHeapUtil(self, root):
		arr = []
		inorder(root, arr)
		troot = util(arr)
		root.data = troot.data
		root.left = troot.left
		root.right = troot.right


class Solution:

	def convertToMaxHeapUtil(self, root):
		arr = []

		def dfs1(root):
			if not root:
				return
			dfs1(root.right)
			arr.append(root.data)
			dfs1(root.left)
		dfs1(root)
		i = 0

		def dfs2(root):
			nonlocal i
			if not root:
				return
			root.data = arr[i]
			i += 1
			dfs2(root.right)
			dfs2(root.left)
		dfs2(root)


def ino(root, v):
	if root == None:
		return
	ino(root.left, v)
	v.append(root.data)
	ino(root.right, v)

def pos(root, v):
	if root == None:
		return
	pos(root.left, v)
	pos(root.right, v)
	root.data = v[-1]
	v.pop()

class Solution:

	def convertToMaxHeapUtil(self, root):
		v = []
		ino(root, v)
		v = v[::-1]
		pos(root, v)


class Solution:

	def convertToMaxHeapUtil(self, root):

		def helper(root):
			if root == None:
				return []
			return helper(root.left) + [root.data] + helper(root.right)
		inorder = helper(root)
		i = 0

		def postorder(root):
			nonlocal i
			if root == None:
				return
			postorder(root.left)
			postorder(root.right)
			root.data = inorder[i]
			i += 1
		postorder(root)
		return root


class Solution:

	def convertToMaxHeapUtil(self, root):
		arr = []
		i = 0

		def ino(node):
			if not node:
				return
			ino(node.left)
			arr.append(node.data)
			ino(node.right)
		ino(root)

		def dfs(node):
			nonlocal i
			if not node:
				return
			dfs(node.left)
			dfs(node.right)
			node.data = arr[i]
			i += 1
		dfs(root)


class Solution:

	def getPostOrder(self, root, in_order):
		if not root:
			return
		self.getPostOrder(root.left, in_order)
		in_order.append(root.data)
		self.getPostOrder(root.right, in_order)
		return

	def traverse(self, root, k, in_order):
		if not root:
			return
		self.traverse(root.left, k, in_order)
		self.traverse(root.right, k, in_order)
		root.data = in_order[k[0]]
		k[0] += 1
		return

	def convertToMaxHeapUtil(self, root):
		in_order = []
		k = [0]
		self.getPostOrder(root, in_order)
		self.traverse(root, k, in_order)
		return


class Solution:

	def convertToMaxHeapUtil(self, root):

		def rajeev(root, a):
			if root == None:
				return a
			a = a + rajeev(root.right, a) + [root.data] + rajeev(root.left, a)
			return a
		s = rajeev(root, [])

		def funk(root, a, i, n):
			if root == None:
				return i
			root.data = a[i]
			i += 1
			i = funk(root.right, a, i, n)
			return funk(root.left, a, i, n)
		funk(root, s, 0, len(s))


import sys
sys.setrecursionlimit(1000000)

class Solution:

	def convertToMaxHeapUtil(self, root):

		def inorder(root):
			if root == None:
				return []
			return inorder(root.left) + [root.data] + inorder(root.right)
		vals = inorder(root)
		global i
		i = 0

		def postorder(root):
			global i
			if root == None:
				return
			postorder(root.left)
			postorder(root.right)
			root.data = vals[i]
			i += 1
		postorder(root)