Flatten Binary Tree to Linked List

Problem statement

A tour organizer converts a branching attraction map into a single walking itinerary. Attractions must appear in the order produced by visiting each root before its left branch and then its right branch. Your task Flatten the binary tree in place into a right-child-only linked chain following preorder traversal. Every left child pointer must become absent, and each right pointer must lead to the next original node. Important details Reuse the original nodes rather than building a separate list of copied values. The final node has no right child. Print the resulting chain from the original root. An empty tree produces an empty chain. Worked example For root 1, left child 2 with child 4, and right child 3, preorder is 1, 2, 4, 3. The flattened right chain must have that order.

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

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

Sample output

1 2 4 3