Convert Binary Tree to Doubly Linked List

You are given a binary tree. Your task is to convert the binary tree into a doubly linked list (DLL) such that the order of the DLL is the same as the inorder traversal of the binary tree. In the resulting doubly linked list, each node's left pointer should point to its previous node and its right pointer should point to its next node.

The conversion must satisfy the following conditions:

• The head of the DLL is the leftmost node of the binary tree.
• If the binary tree is empty, the resulting DLL is also empty.

You can represent the binary tree using level order input (with null representing a missing node). The expected output is the data from nodes of the DLL printed in order from head to tail, separated by a space.

Recall that the inorder traversal of a binary tree is defined as:

$$\text{inorder}(node)=\begin{cases} \text{inorder}(node.left) \\ node.data \\ \text{inorder}(node.right) \end{cases}$$

inputFormat

The input is given as a single line containing the level order traversal of the binary tree, with each value separated by a space. Use the string null to denote a missing node.

For example: 10 12 15 25 30 36 null

outputFormat

Print the values of the nodes in the resulting doubly linked list from head to tail, separated by a single space. If the tree is empty, output nothing.

## sample

10 12 15 25 30 36 null

25 12 30 10 36 15