BST to Min Heap

Moderate
0/80
2 upvotes

Problem statement

You are given a binary search tree which is also a complete binary tree. You have to convert the given BST into a Min 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.

A binary search tree (BST) is a binary tree data structure which has the following properties.

• The left subtree of a node contains only nodes with data less than the node’s data.
• The right subtree of a node contains only nodes with data greater than the node’s data.
• Both the left and right subtrees must also be binary search trees.

A Binary Tree is a Complete Binary Tree if all the levels are completely filled except possibly the last level and the last level has all keys as left as possible.

A Min Heap is a binary tree in which the value in each internal node is smaller than or equal to the values in the children of that node. In this problem, there is also a 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.

Note : 
You do not need to print anything, just return the root of the Min Heap
Detailed explanation ( Input/output format, Notes, Images )
Input Format 
The first line of input contains an integer 'T' representing the number of test cases. Then the test cases follow.

The only line of each test case contains elements in the level order form. The line consists of values of nodes separated by a single space. In case a node is null, we take -1 on its place.

For example, the input for the tree depicted in the below image would be :

image

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

Explanation :

Level 1 :
The root node of the tree is 4

Level 2 :
Left child of 4 = 2
Right child of 4 = 6

Level 3 :
Left child of 2 = 1
Right child of 2 = 3
Left child of 6 = 5
Right child of 6 = 7

Level 4 :
Left child of 1 = null (-1)
Right child of 1 = null (-1)
Left child of 3 = null (-1)
Right child of 3 = null (-1)
Left child of 5 = null (-1)
Right child of 5 = null (-1)
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:

4 2 6 1 3 5 7 -1 -1 -1 -1 -1 -1
Output Format : 
For each test case, print the Min Heap in the level order form.

The output for each test case is in a separate line.
Constraints : 
1 <= T <= 10
1 <= N <= 5 * 10^4
-10^9 <= data <= 10^9 and data != -1

Where N is the number of nodes in the tree.
Sample Input 1:
1
4 2 6 1 3 5 7 -1 -1 -1 -1 -1 -1 -1 -1
Sample Output 1:
1 2 5 3 4 6 7 -1 -1 -1 -1 -1 -1 -1 -1
Explanation of the Sample Input 1:

sample

The level order traversal of the heap is 1 2 5 3 4 6 7 -1 -1 -1 -1 -1 -1.
Sample Input 2:
1
1 0 -1 -1 -1
Sample Output 2:
0 1 -1 -1 -1
Hint

Change the node value of BST such that it becomes Min heap.

Approaches (1)
Tree Traversal

It is given that the given BST is also a complete binary tree, it means if we change the node values according to properties of the heap, we will get the Min Heap.
 

Here is the algorithm-

  • Store the node values in an array ‘inorderArray’ in sorted order. We can do this using a simple inorder traversal in BST.
    • In inorder traversal, for every node, its left subtree is visited, and then the node is visited, and then its right subtree.
  • Make a variable ‘idx’, which will be initially 0.
  • Now we will traverse the BST using preorder order traversal. While traversing a node we will change its value to ‘inorderArry[idx]’ and increment ‘idx’ by 1.
    • In preorder traversal, for every node, the node is visited(the data is stored in the array), and then its left subtree is visited, and then its right subtree.
Time Complexity

O(N), Where N is the number of nodes in the BST.
 

We are traversing the BST twice and traversing the BST takes O(N) time, thus the final time complexity is O(2 * N) ~ O(N).

Space Complexity

O(N), Where N is the number of nodes in the BST.
 

During traversal, O(H) recursion stack space is used, where H is the height of BST. In case of skewed trees, H = N, hence, the overall complexity is O(N).

Code Solution
(100% EXP penalty)
BST to Min Heap
Full screen
Console