Zigzag Level Order Traversal of a Binary Tree

You are given a binary tree with N nodes, each with a unique value from 1 to N. The binary tree is described by a list of edges. Each edge provides a connection from a parent node to a child node along with a character indicating whether the child is a left ('L') or right ('R') child.

Your task is to perform a zigzag level order traversal of the tree. In a zigzag (or spiral) traversal, the nodes at the first level are processed from left to right, the second level from right to left, the third level from left to right, and so on.

Input Format: The first line contains the integer N, the number of nodes. This is followed by N-1 lines, each containing two integers U and V and a character C (either 'L' or 'R') representing an edge from node U to node V.

Output Format: Print the zigzag level order traversal of the tree. All node values should be printed on one line separated by a single space.

The process requires you to build the tree from the input and then traverse it in the required zigzag order.

inputFormat

The input starts with an integer N (the number of nodes). The next N-1 lines each contains two integers U and V and a character C separated by spaces, where C is either 'L' (left child) or 'R' (right child).

outputFormat

A single line containing the zigzag level order traversal of the tree, with each node value separated by a space.## sample

7
1 2 L
1 3 R
2 4 L
2 5 R
3 6 L
3 7 R

1 3 2 4 5 6 7