Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place following its preorder traversal. That is, after flattening, the left child of every node should be null and the right child should point to the next node in the preorder sequence. Formally, if the initial tree has N nodes, your algorithm should run in O(N) time and use O(N) space in the worst case. The flatten operation transforms the binary tree into a structure that is similar to a singly linked list using the original tree's right pointers. Use the algorithm: \(\texttt{flatten(root)}\).

inputFormat

The input is provided via standard input (stdin) as a single line of space-separated tokens representing the pre-order traversal of the binary tree. Each token is either an integer or the string null (which represents a missing node). For example, a tree with a single node is represented as:

1 null null

outputFormat

Output the flattened binary tree’s node values in order by following the right pointers, separated by a single space. Output is printed via standard output (stdout). For an empty tree, output an empty line.

1 null null

1