Zigzag Binary Tree Traversal Problem

Given a binary tree, compute the zigzag level order traversal of the node values in the tree. The zigzag traversal requires traversing levels from left to right, then right to left for the next level, and alternating accordingly.

Input:

It starts with an integer 'T', representing the number of test cases. Each test case consists of a single line of space-separated integers representing nodes in level order. If a node is null, it is denoted by -1. The -1 will not be included in the actual nodes.

Output:

For each test case, output the zigzag level order traversal of the binary tree, with values separated by a single space. Print each test case result on a new line.

Example:

Input:

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

Output:

1 3 2 4 5 6 7

The example represents a binary tree where, starting from the root, level by level, the output reflects zigzag traversal.

Constraints:

• 1 <= T <= 100
• 0 <= N <= 3000
• 0 <= val <= 10⁵

Where ‘T’ is the number of test cases, ‘N’ is the total number of nodes in the binary tree, and “val” is the value of the binary tree node.

Time Limit: 1 sec