Invert a Binary Tree

You are provided with a Binary Tree and one of its leaf nodes. Your task is to invert this binary tree, making sure to adhere to the following guidelines:

• The given leaf node becomes the root after the inversion.
• For a node (say, ‘x’):
  • If there exists a left child that is not yet taken, it must become the right child of ‘x’.
  • If the left child is already taken, then the right child remains on the right side of ‘x’.
• The parent of ‘x’ must become the left child of ‘x’.

Input:

The first line contains a single integer ‘T’ representing the number of test cases.

The first line of each test case will contain a single TreeNode “leaf” which denotes one of the leaf nodes of the given binary tree.

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

For example, a tree's input could be:

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

The above format is structured as follows:
 - Level 1: The root node of the tree is 1.
 - Level 2: Left child of 1 = 2, Right child of 1 = 3.
 - Level 3: Left child of 2 = 4, Right child of 2 = null (-1), Left child of 3 = 5, Right child of 3 = 6.
 - Level 4: Left child of 4 = null (-1), Right child of 4 = 7, Left & Right children of 5 and 6 = null (-1).
 - Level 5: Left & Right child of 7 = null (-1).

The sequence is formed by reading level by level, ending when all nodes at the last level are null(-1).

Output:

For each test case, return the whole binary tree after considering the given leaf node as the new root node.

Output for every test case will be printed on a separate line.

Note: Provide the output in the same sequence and format as the input.

Example:

Input:

The input will be: 1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

Output:

The output depends on the inversion process according to the guidelines defined.

Constraints:

• 1 <= T <= 50
• 1 <= N <= 10000
• -10^5 <= DATA <= 10^5
• The leaf is one of the leaf nodes of the given binary tree.
• Time limit: 1 sec

Note:

You don’t need to print anything; It has already been taken care of. Just implement the given function.

The tree will only have distinct node values.