Binary Tree to BST Transformation Task

Given a binary tree consisting of 'N' nodes with distinct integer values, transform it into a Binary Search Tree (BST) while maintaining the original structure of the binary tree.

Explanation:

The transformation should maintain the shape of the original binary tree. A Binary Search Tree (BST) adheres to the following rules:

• Nodes in the left subtree hold values less than the node's value.
 • Nodes in the right subtree hold values greater than the node's value.
 • Both subtrees must themselves be binary search trees.

Input:

The first line contains an integer 'T' representing the number of test cases.
Each test case is described as a single line containing space-separated integers representing the binary tree's level order traversal.
If a node is absent, '-1' is used in its place.

Output:

For each test case, return the level order traversal of the transformed BST as a single line.

Example:

Given Binary Tree:

Diagram depicting the input binary tree structure

Resulting BST:

Diagram depicting the resulting BST structure

Constraints:

• 1 ≤ T ≤ 10^2
• 1 ≤ N ≤ 5 * 10^3
• 0 ≤ data ≤ 10^5 and data ≠ -1

Time Limit: 1 sec

Note:

No output function is required; focus on implementing the transformation function.