Ninja And The Tree Problem Statement

Ninja, while learning Binary Search Trees (BST), accidentally swapped two nodes in her self-constructed BST. Your task is to help Ninja by correcting the BST so that all properties of a BST are satisfied.

Input:

The first line contains an integer 'T' which denotes the number of test cases.

For each test case, a single line contains the elements of the tree in level order form, separated by a single space. If a node doesn't have a left or right child, take -1 in its place.

Output:

For each test case, output the corrected Binary Search Tree in level order form. Each test case output should be on a separate line.

Example:

Input:

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

Output:

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

Explanation:

The input in level order first describes the root node, followed by its children from left to right, continuing level by level. Nodes without children are represented with -1.

Constraints:

• 1 <= T <= 100
• 2 <= N <= 5000, where 'N' is the number of nodes.
• 0 <= X <= 2^31 - 1, where 'X' is the value at a node.
• Time limit: 1 second

Note:

The sequence of input ends when all nodes at the last level are null (-1). You are not required to print anything; it has already been handled. Just implement the function to return the corrected BST.