Inorder Traversal of Binary Tree Without Recursion

Given a Binary Tree consisting of 'N' nodes with integer values, your task is to perform an In-Order traversal of the tree without using recursion.

Input:

The first line contains an integer 'T' representing the number of test cases. The first line of each test case contains the tree elements in level order format. Values are separated by a single space, using '-1' for null nodes.

Output:

For each test case, return a list with the In-Order traversal of the binary tree. Output each traversal as a single line of 'N' space-separated integers.

Example:

Input:

1
1 3 8 5 2 7 -1 -1 -1 -1 -1 -1 -1

Output:

5 3 2 1 7 8

Constraints:

• 1 <= T <= 10
• 0 <= N <= 3000
• 0 <= data <= 10^9

Note:

• You are not required to print the output; just implement the function to return the result.
• This input format represents the tree in level order, with nodes at the last level denoted by -1 to indicate null values.