Binary Tree to Doubly Linked List

Transform a given Binary Tree into a Doubly Linked List.

Ensure that the nodes in the Doubly Linked List follow the Inorder Traversal of the Binary Tree.

Input:

The first line contains an integer 'T' representing the number of test cases. For each test case, provide the tree nodes in level order as a single space-separated string of integers. Use -1 to denote null nodes.

Output:

For each test case, return the head of the Doubly Linked List.

Example:

Input:

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

Output:

The head to the doubly linked list with elements in order: 4 -> 2 -> 7 -> 1 -> 5 -> 3 -> 6

Constraints:

• 1 ≤ T ≤ 100
• 0 ≤ N ≤ 3000
• -10^6 ≤ data ≤ 10^6 and data ≠ -1

Note:

Output is handled internally. Implement the function to perform the conversion.