Binary Tree Traversals

Given a binary tree with \( n \) nodes (where \( n \leq 10^6 \)), numbered from \( 1 \) to \( n \). For each node, two integers are provided representing its left and right child respectively (if a node is a leaf, the children are given as \( 0\ 0 \)). Node \( 1 \) is the root of the tree.

After building the tree, perform and output its pre-order, in-order, and post-order traversals, each on a separate line. In each traversal, output the node indices separated by a single space.

inputFormat

The first line contains an integer \( n \) indicating the number of nodes.

Then follow \( n \) lines; the \( i \)-th line (1-indexed) contains two integers representing the left and right children of node \( i \). A value of \( 0 \) indicates that the child does not exist.

outputFormat

Output three lines:

1. The first line contains the pre-order traversal.
2. The second line contains the in-order traversal.
3. The third line contains the post-order traversal.

Each traversal should list the node numbers separated by a space.

sample

3
2 3
0 0
0 0

1 2 3
2 1 3
2 3 1