Convert BST to Min Heap

You are given a binary search tree (BST) that is also a complete binary tree. Your task is to convert this BST into a Min Heap. The resultant Min Heap should maintain the property that all values in the left subtree of a node are less than all the values in the right subtree of the node.

A binary search tree (BST) is defined by 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 complete binary tree is one where all levels are completely filled except possibly for the last level, which should have all keys as left as possible.

A Min Heap is defined as a binary tree where the value of each node is smaller than or equal to the values in its children. For this problem, there is an additional requirement that all values in the left subtree of a node should be less than all the values in the right subtree.

Input:

The first line contains an integer 'T', representing the number of test cases. The subsequent lines represent each test case, containing values of nodes in level order form separated by spaces. Use -1 to denote a null node.

Output:

For each test case, print the Min Heap in level order form. Separate the output of each test case with a new line.

Example:

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

Output:
1 2 5 4 3 6 7

Constraints:

• 1 <= T <= 10
• 1 <= N <= 5 * 10^4
• -10^9 <= data <= 10^9, and data != -1

Note:

You do not need to print anything. Your function should return the root of the Min Heap. The provided input-output format is to ensure clarity.