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:

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

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

Output

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

# 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

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

Complexity Analysis:

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