Fixing a Swapped Binary Search Tree

Given a Binary Search Tree (BST) where two nodes have been swapped by mistake, your task is to restore or fix the BST without changing its structure.

Input:

The first line of input contains an integer T, representing the number of test cases.
The first line of each test case contains the elements of the tree in level order form, separated by spaces in a single line. The value -1 denotes a null node.

Output:

For each test case, output the level order traversal of the restored tree in a separate line.

Example:

Input:

1
20 30 35 5 15 10 42 -1 -1 13 -1 -1 -1 -1 -1 -1 -1

Output:

20 5 35 30 15 10 42 13

Constraints:

• 1 <= T <= 100
• 1 <= N <= 10^3
• 0 <= data <= 10^9 where 'data' denotes the value of the nodes in the given tree.
• Time limit: 1 second

Note:

The BST will not contain duplicate nodes. The input format description provides clarity on how level order input is structured. No extra space other than the recursion stack should be used to solve this problem.