Spiral Order Traversal of a Binary Tree

Given a binary tree, output the values of its nodes in spiral (zigzag) order. In spiral order traversal, nodes on alternate levels are traversed from left to right and then right to left.

Input is provided as a level order sequence of node values with each value separated by a space; a token of N represents a NULL node (i.e. a missing child).

inputFormat

A single line containing the level order traversal of the binary tree's nodes. Each value is separated by a space. Use N to denote a NULL node.

outputFormat

A single line containing the spiral order traversal of the binary tree nodes. The node values must be printed in order separated by a single space. If the tree is empty, output nothing.## sample

1 2 3 4 5 6 7

1 3 2 4 5 6 7