Preorder Traversal of a Binary Tree

Given a binary tree provided as a single line string in level-order format (with node values separated by spaces and missing nodes denoted by null), output its preorder traversal (i.e. visit the root first, then the left subtree, followed by the right subtree).

The preorder traversal for a binary tree \(T\) is defined recursively as follows:

\[ \text{Preorder}(T) = \begin{cases} [] & \text{if } T \text{ is empty}, \\ [\text{root}] \, \Vert \, \text{Preorder}(T_{left}) \Vert \, \text{Preorder}(T_{right}) & \text{otherwise}, \end{cases} \] where \(\Vert\) denotes the concatenation of sequences.

inputFormat

The input is a single line string representing the binary tree in level-order. The node values are separated by spaces. If a node is missing, it is represented by the string null.

For example: 1 2 3 null null 4 5

outputFormat

Output the preorder traversal of the binary tree. The output should be the node values printed in one line separated by spaces.

sample

1 2 3

1 2 3