Zigzag Traversal of Binary Tree

Given a binary tree with integer values in its nodes, your task is to print the zigzag traversal of the tree.

Note:

In zigzag order, level 1 is printed from left to right, level 2 from right to left, and level 3 from left to right again, alternating in this pattern.

Example:

Input:

The binary tree is:
 1
 / \
3   8
/|   |\
5 2 7  -1
 -1  -1 -1
-1 -1
-1 -1

Output:

[1, 4, 3, 5, 2, 7, 6]

Explanation:

Level 1: Root node is 1
Level 2: Nodes are 3 and 8, traversed from right to left
Level 3: Nodes are 5, 2, and 7, traversed from left to right

Constraints:

• 1 <= 'T' <= 100
• 0 <= 'N' <= 10^3
• 0 <= 'NODES' <= 10^9
• Time Limit: 1 second

Input:

The first line contains an integer 'T' denoting the number of test cases. For each test case, provide the tree elements in level order. Use -1 for null nodes. For example:
1
3 8
5 2 7 -1
-1 -1 -1 -1 -1 -1

Output:

For each test case, print the nodes in zigzag order traversal on a new line, separated by a single space.

Note:

The function implementation is required only; nothing is to be printed as it has been taken care of.