Problem title
Difficulty
Avg time to solve

Subsets II
Moderate
45 mins
Palindromic Substrings
Moderate
20 mins
Minimum Cost Path
Moderate
25 mins
Make Maximum Number
Moderate
18 mins
Algorithm to find best insert position in sorted array
Easy
10 mins
Convert binary tree to mirror tree
Easy
15 mins
Sort An Array According To The Count Of Set Bits
Moderate
25 mins
Minimum Length Of Compressed String
Ninja
60 mins
Print the array after K operations
Easy
15 mins
Convert A Given Binary Tree To Doubly Linked List
Moderate
15 mins
15

Convert BST to Min Heap

Difficulty: MEDIUM
Avg. time to solve
25 min
Success Rate
70%

Problem Statement

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.
Sample Input 1:
1
8 5 10 2 6 -1 -1 -1 -1 -1 7 -1 -1
10 7 11 1 8 -1 -1 -1 -1 -1 -1 
Sample Output 1:
2 5 6 7 8 10
1 7 8 10 11
Explanation of sample input 1:
Test-Case 1 : 
Converting the BST into min-heap and its pre-order printing would look like: 2 5 6 7 8 10.

Test-Case 2 :
Converting the BST into min-heap and its pre-order printing would look like: 2 5 6 7 8 10.
Sample Input 2:
2
4 2 6 1 3 5 7 -1 -1 -1 -1 -1 -1 -1 -1
2 1 3 -1 -1 -1 -1
Sample Output 2:
1 2 3 4 5 6 7
1 2 3    
Reset Code
Full screen
copy-code
Console