Binary Tree Inorder Traversal

Problem statement

A binary catalog places a group of records on the left of each entry and another group on its right. An archivist needs a traversal that visits the complete left group, then the entry itself, and finally the right group, applying the same rule recursively. Your task Return the inorder traversal of the binary tree: left subtree, node, right subtree. Important details This is not necessarily a search tree, so the output need not be sorted. Node indices describe links and are not the values to print. Visit every existing node exactly once, and return an empty sequence for an empty tree. Worked example For root 4 with left child 7 and right child 2, the inorder traversal is 7 4 2. Structural order determines the result even though the values are not increasing.

Input format

The first line contains n. The next n lines contain value left right for nodes 0 through n-1. Child indices are -1 when absent. Node 0 is the root when n > 0. The records form one valid binary tree; n = 0 represents an empty tree.

Output format

Print the resulting values in order, separated by spaces. Print EMPTY if there are no values.

Constraints

0 <= n <= 2000; -1000 <= value <= 1000. Child indices are -1 or valid node indices; no cycles or shared children.

Sample input

3
4 1 2
7 -1 -1
2 -1 -1

Sample output

7 4 2