# Convert BST to Max Heap

Given a **Binary Search Tree** which is also a Complete Binary Tree. The problem is to 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 to all the nodes in the so-converted Max Heap. 

**Examples:**  

```plaintext
Input:          4
               /   \
              2     6
            /  \   /  \
           1   3  5    7  
 
Output:        7
             /   \
            3     6
          /   \  /   \
         1    2 4     5
The given BST has been transformed into a
Max Heap.
All the nodes in the Max Heap satisfy the given
condition, that is, values in the left subtree of
a node should be less than the values in the right
a subtree of the node. 
```

**Approach** **1 :**

1. Create an array **arr\[\]** of size n, where n is the number of nodes in the given BST. 
    
2. Perform the inorder traversal of the BST and copy the node values in the **arr\[\]** in sorted   
    order. 
    
3. Now perform the postorder traversal of the tree. 
    
4. While traversing the root during the postorder traversal, one by one copy the values from the array **arr\[\]** to the nodes. 
    

**Implementation:**

python

```plaintext
# Python3 implementation to convert a given
# BST to Max Heap
i = 0
class Node:
	def __init__(self):
		self.data = 0
		self.left = None
		self.right = None

# Helper function that allocates a new node
# with the given data and None left and right
# pointers.
def getNode(data):

	newNode = Node()
	newNode.data = data
	newNode.left = newNode.right = None
	return newNode

arr = []

# Function for the inorder traversal of the tree
# so as to store the node values in 'arr' in
# sorted order
def inorderTraversal( root):

	if (root == None):
		return arr

	# first recur on left subtree
	inorderTraversal(root.left)

	# then copy the data of the node
	arr.append(root.data)

	# now recur for right subtree
	inorderTraversal(root.right)

def BSTToMaxHeap(root):

	global i
	if (root == None):
		return None

	# recur on left subtree
	root.left = BSTToMaxHeap(root.left)

	# recur on right subtree
	root.right = BSTToMaxHeap(root.right)

	# copy data at index 'i' of 'arr' to
	# the node
	root.data = arr[i]
	i = i + 1
	return root

# Utility function to convert the given BST to
# MAX HEAP
def convertToMaxHeapUtil( root):
	global i
	
	# vector to store the data of all the
	# nodes of the BST
	i = 0

	# inorder traversal to populate 'arr'
	inorderTraversal(root)

	# BST to MAX HEAP conversion
	root = BSTToMaxHeap(root)
	return root

# Function to Print Postorder Traversal of the tree
def postorderTraversal(root):

	if (root == None):
		return

	# recur on left subtree
	postorderTraversal(root.left)

	# then recur on right subtree
	postorderTraversal(root.right)

	# print the root's data
	print(root.data ,end= " ")

# Driver Code

# BST formation
root = getNode(4)
root.left = getNode(2)
root.right = getNode(6)
root.left.left = getNode(1)
root.left.right = getNode(3)
root.right.left = getNode(5)
root.right.right = getNode(7)

root = convertToMaxHeapUtil(root)
print("Postorder Traversal of Tree:" )
postorderTraversal(root)

```

<table><tbody><tr><td colspan="1" rowspan="1"><p></p></td></tr></tbody></table>

**Output**

```plaintext
Postorder Traversal of Tree:
1 2 3 4 5 6 7 
```

**Complexity Analysis:**

* **Time Complexity: O(n)** 
    
* **Auxiliary Space: O(n)**
    

**Approach 2 : (Using Heapify Up/Max Heap)**

1. Create an array q\[\] of size n, where n is the number of nodes in the given BST. 
    
2. Traverse the BST and append each node into the array using level order traversal.
    
3. Call heapify\_up to create max-heap for each element in array q\[\] from 1 to n so that the array q\[\] will be arranged in descending order using max-heap.
    
4. Update the root and child of each node of the tree using array q\[\] like creating a new tree from array q\[\].
    

**Implementation:**

python

```plaintext
# User function Template for python3
class Node:
	def __init__(self):
		self.data = 0
		self.left = None
		self.right = None


# Helper function that allocates a new node
# with the given data and None left and right
# pointers.
def getNode(data):
	newNode = Node()
	newNode.data = data
	newNode.left = newNode.right = None
	return newNode

# To find parent index
def parent(i):
	return (i - 1) // 2

# heapify_up to arrange like max-heap
def heapify_up(q, i):
	while i > 0 and q[parent(i)].data < q[i].data:
		q[parent(i)], q[i] = q[i], q[parent(i)]
		i = parent(i)


def convertToMaxHeapUtil(root):
	if root is None:
		return root

	# creating list for BST nodes
	q = []
	q.append(root)
	i = 0
	while len(q) != i:
		if q[i].left is not None:
			q.append(q[i].left)
		if q[i].right is not None:
			q.append(q[i].right)
		i += 1
	# calling max-heap for each iteration
	for i in range(1, len(q)):
		heapify_up(q, i)

	# updating root as max value in heap
	root = q[0]
	i = 0

	# updating left and right nodes of BST using list
	while i < len(q):
		if 2 * i + 1 < len(q):
			q[i].left = q[2 * i + 1]
		else:
			q[i].left = None
		if 2 * i + 2 < len(q):
			q[i].right = q[2 * i + 2]
		else:
			q[i].right = None
		i += 1
	return root


# Function to Print Postorder Traversal of the tree
def postorderTraversal(root):
	if (root == None):
		return

	# recur on left subtree
	postorderTraversal(root.left)

	# then recur on right subtree
	postorderTraversal(root.right)

	# print the root's data
	print(root.data, end=" ")


# Driver Code

# BST formation
root = getNode(4)
root.left = getNode(2)
root.right = getNode(6)
root.left.left = getNode(1)
root.left.right = getNode(3)
root.right.left = getNode(5)
root.right.right = getNode(7)

root = convertToMaxHeapUtil(root)
print("Postorder Traversal of Tree:")
postorderTraversal(root)


```

**Output**

```plaintext
Postorder Traversal of Tree:
1 2 3 4 5 6 7 
```

**Complexity Analysis:**

**Time Complexity**: O(n)   
**Auxiliary Space**: O(n)