Convert BST to Sorted Doubly Linked List

You are given a binary search tree (BST) and your task is to convert it in-place into a sorted doubly linked list. In a BST, for every node, all values in the left subtree are less than the node’s value and all values in the right subtree are greater, i.e., \(\text{left.val} < \text{node.val} < \text{right.val}\). Using an in-order traversal will yield the nodes in ascending order. The doubly linked list should use the left pointer of each node as the previous pointer and the right pointer as the next pointer.

If the BST is empty, your program should output an empty line.

inputFormat

The input is provided via standard input (stdin). The first line contains an integer n representing the number of nodes. If n is not zero, the next line contains n space-separated integers in strictly increasing order which represent the node values (i.e. the in-order traversal of the BST).

outputFormat

Output via standard output (stdout) the values of the resulting doubly linked list from head to tail in one line, with each value separated by a single space. If the BST is empty, output an empty line.

7
4 6 8 10 12 14 16

4 6 8 10 12 14 16