BST to Doubly Linked List Conversion

Given a binary search tree (BST), convert it in-place into a sorted doubly linked list following an in-order traversal. The doubly linked list should contain the nodes of the BST in ascending order.

Note that the time complexity of your solution should be \(O(n)\) and the space complexity (excluding the output list) is \(O(n)\) due to the recursion stack. Your program will read the BST in a level-order format from standard input and output the values of the doubly linked list from head to tail to standard output.

The BST is given in a single line as space-separated tokens. The token "null" represents a missing node. For example, the input 2 1 3 represents a BST with 2 as the root, 1 as the left child, and 3 as the right child.

inputFormat

The input consists of a single line containing the level-order traversal of the BST. Nodes are given as space-separated tokens. If a node is missing, it will be indicated by the string "null". For example:

2 1 3

outputFormat

Output the values of the converted doubly linked list in order (from head to tail) on a single line, with each value separated by a single space. If the BST is empty, output an empty line.

## sample

1

1

</p>