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

Question

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

Accepted Answer

Zigzag level order traversal of a binary tree is computed by alternating between left to right and right to left traversal at each level.

Use a queue to perform level order traversal of the binary tree.
Maintain a flag to switch between left to right and right to left traversal at each level.
Store the node values in a list while traversing and alternate the order based on the flag.
Example: For input 1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1, the zigzag traversal output is 1 3 2 4 5 6 7.