Binary Tree Zigzag Traversal Problem Statement

Given a Binary Tree comprised of 'N' nodes with integer values, your task is to print the zigzag traversal of the tree.

Note:

The zigzag pattern implies that the first level is traversed from left to right, the second level from right to left, and this pattern continues alternately for subsequent levels.

Example:

Input:

The following binary tree:

Output:

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

Input:

The first line contains an integer 'T' representing the number of test cases. For each test case, the input follows: The line contains elements of the tree in level order form, with values of nodes separated by spaces. Use -1 for null nodes. Example: 1 3 8 5 2 7 -1 -1 -1 -1 -1 -1 -1

Output:

For each test case, print the zigzag order traversal of nodes in a single line, with values separated by spaces.

Constraints:

1

Question

Binary Tree Zigzag Traversal Problem Statement

Given a Binary Tree comprised of 'N' nodes with integer values, your task is to print the zigzag traversal of the tree.

Note:

The zigzag pattern implies that the first level is traversed from left to right, the second level from right to left, and this pattern continues alternately for subsequent levels.

Example:

Input:

The following binary tree:

Output:

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

Input:

The first line contains an integer 'T' representing the number of test cases. For each test case, the input follows: 
The line contains elements of the tree in level order form, with values of nodes separated by spaces. Use -1 for null nodes.

Example:
1 3 8 5 2 7 -1 -1 -1 -1 -1 -1 -1

Output:

For each test case, print the zigzag order traversal of nodes in a single line, with values separated by spaces.

Constraints:

1 <= 'T' <= 100
0 <= 'N' <= 10^3
0 <= 'NODES' <= 10^9

You do not need to handle input/output in your solution. Implement the function as directed.

Accepted Answer

Implement a function to print the zigzag traversal of a Binary Tree.

Traverse the Binary Tree level by level, alternating the direction of traversal for each level.
Use a queue to keep track of nodes at each level and a flag to switch the direction of traversal.
Print the values of nodes in the zigzag order as described in the problem statement.

Binary Tree Zigzag Traversal Problem Statement

Note:

Example:

Input:

Output:

Input:

Output:

Constraints:

PubMatic SDE-2 interview questions & answers

Popular interview questions of SDE-2