Convert Binary Tree to Doubly Linked List

You are given a binary tree and your task is to convert it into a doubly linked list (DLL) following the in-order traversal order. Each node in the DLL should have the same value as in the original binary tree.

The binary tree is represented with an integer N on the first line representing the number of nodes. The following N lines each contain three integers: the node's value, the left child's value, and the right child's value. A value of -1 indicates that the child is null.

After constructing the binary tree, perform an in-order traversal to create the DLL. Finally, output the values of the DLL nodes in order, separated by a single space.

Note: The in-order traversal for a node is defined as:

\[ \text{inorder}(node) = \begin{cases} \text{inorder}(node.left) \quad \text{visit } node \quad \text{inorder}(node.right), & \text{if } node \neq null \\ \text{(do nothing)}, & \text{if } node = null \end{cases} \]

inputFormat

The input is read from stdin and consists of:

• A single integer N on the first line which represents the number of nodes in the tree.
• Each of the next N lines contains three integers: the value of the node, the value of its left child, and the value of its right child. A value of -1 indicates that a child is absent.

outputFormat

Output to stdout a single line containing the values of the nodes in the doubly linked list after conversion, following the in-order traversal order. The values should be separated by a single space.

## sample

5
10 5 15
5 -1 7
7 -1 -1
15 12 20
12 -1 -1
20 -1 -1

5 7 10 12 15 20