Convert BST to Min Heap

Posted: 3 Dec, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You are given a 'ROOT' of a binary search tree of integers. The given BST is also a complete binary tree.

Your task is to convert the given binary search tree into a Min Heap and print the preorder traversal of the updated binary search tree.

Note:

Binary Search Tree is a node-based binary tree data structure that has the following properties:

1. The left subtree of a node contains only nodes with keys lesser than the node’s key.
2. The right subtree of a node contains only nodes with keys greater than the node’s key.
3. The left and right subtree each must also be a binary search tree.

A Binary Heap is a Binary Tree with the following property:

1. It’s a complete tree (all levels are filled except possibly the last level and the last level has all keys as left as possible). This property of Binary Heap makes them suitable to be stored in an array.

A Binary Heap is either Min Heap or Max Heap. In a Min Binary Heap, the key at the root must be minimum among all keys present in Binary Heap. The same property must be recursively true for all nodes in Binary Tree. Max Binary Heap is similar to Min Heap.

For example:

Given:- BST’s ‘ROOT’ = 4 2 6 -1 -1 -1 -1 
Then the min-heap in pre-order fashion would be 2 4 6.

Input format :

The first line of input contains an integer ‘T’ denoting the number of test cases.

The next ‘T’ lines contain a Binary Search Tree in a Level order fashion where -1 denotes NULL nodes.

Example:

The input for the tree depicted in the below image will be:

alt text

1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1

Explanation :

Level 1 :
The root node of the tree is 1

Level 2 :
Left child of 1 = 2
Right child of 1 = 3

Level 3 :
Left child of 2 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 = 6

Level 4 :
Left child of 4 = null (-1)
Right child of 4 = 7
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)

Level 5 :
Left child of 7 = null (-1)
Right child of 7 = null (-1)

The first not-null node(of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.
The input ends when all nodes at the last level are null(-1).
Note :
The above format was just to provide clarity on how the input is formed for a given tree. 
The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:

1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

Output format :

For each test case, print a single line containing all the Min Heap nodes in a preorder fashion.

The output of each test case will be printed in a separate line.

Note:

You don’t need to print anything, it has already been taken care of. You just need to implement the given function.

Constraints:

1 <= T <= 5
1 <= N <= 2 ^ 10

Where ‘N’ is the number of nodes in a binary search tree.

Time limit: 1 sec.
Approach 1

The main idea is to maintain an array that contains nodes in sorted order. Then traverse the tree again and assign the current node the data in array serial-wise.

 

  • Maintain an array ‘ARRAYWITHNODES’, which will contain all the nodes.
  • Do an ‘INORDERTRAVERSAL’ and push the elements in the array, since for a BST inorder traversal gives elements in sorted order, the elements in the array will be sorted by default.
  • Use a helper function ‘CONVERTTOHEAP’ which has the following parameter :
    • Address of the current node denoted by ‘ROOT’
    • ‘ARRAYWITHNODES’
    • ‘IDX’ to point to the element we assign to the node.
  • Then return the ‘ROOT’ of the heap.
Try Problem