Spiral Order Traversal of a Binary Tree

Given a binary tree with N nodes, your task is to output the Spiral Order traversal of the binary tree.

Input:

The input consists of a single line containing elements of the binary tree provided in level order. The node values are separated by a space, and -1 represents a null node.

Output:

A line of N space-separated integers representing the spiral order traversal of the binary tree.

Example:

Input: 1 2 3 -1 -1 4 5 Output: 1 3 2 4 5

Explanation:

The binary tree corresponding to the input is: 1 / \ 2 3 / \ 4 5 The Spiral Order traversal is: 1 3 2 4 5

Constraints:

0

Question

Spiral Order Traversal of a Binary Tree

Given a binary tree with N nodes, your task is to output the Spiral Order traversal of the binary tree.

Input:

The input consists of a single line containing elements of the binary tree provided in level order. The node values are separated by a space, and -1 represents a null node.

Output:

A line of N space-separated integers representing the spiral order traversal of the binary tree.

Example:

Input: 1 2 3 -1 -1 4 5
Output: 1 3 2 4 5

Explanation:

The binary tree corresponding to the input is:
    1
   / \
  2   3
     / \
    4   5
 The Spiral Order traversal is: 1 3 2 4 5

Constraints:

0 <= N <= 10^4
Where N is the total number of nodes in the binary tree.
Time Limit: 1 second

Note:

You are only required to implement the function that returns the spiral order traversal as a list. All input/output handling has been taken care of.

Accepted Answer

Implement a function to output the Spiral Order traversal of a binary tree given in level order.

Traverse the binary tree in a spiral order, alternating between left to right and right to left at each level.
Use a queue to keep track of nodes at each level and a stack to reverse the order of nodes at odd levels.
Handle null nodes appropriately to maintain the spiral order traversal.
Example: Input: 1 2 3 -1 -1 4 5, Output: 1 3 2 4 5

Asked in Arcesium