# In-order traversal of a binary tree

In-order traversal of a tree is a recursive procedure, where you first visit a the left subtree of a node, then the node itself, and then its right subtree:
1. Visit the left subtree (`node.left`)
1. Visit the current node
1. Visit the right subtree (`node.right`)
Itβs like hanging the binary tree from the root and then reading its values from left to right.
Given a binary tree, you are asked to perform an in-order traversal on it.

#### Input

The input contains space-separated integers representing the values in the nodes of the binary tree. The order of the values is given by traversing from the left to the right subtree every time. A value of 0 means that the node does not exist. Itβs guaranteed that the input binary tree is valid.

#### Output

The program should print the values in the nodes of a binary tree when performing an in-order traversal. All the values should be separated by a space.

#### Examples

 Input Output 1 2 3 4 5 8 9 0 0 0 0 0 0 6 7 0 0 0 0 8 4 9 2 5 1 6 3 7 1 2 3 4 5 8 0 0 0 0 0 6 7 0 0 0 0 8 4 2 5 1 6 3 7 1 2 3 4 5 0 0 0 0 6 7 0 0 8 9 0 0 0 0 4 2 5 1 6 3 8 7 9 1 2 3 4 5 0 0 7 8 0 0 0 0 0 6 0 0 4 2 7 5 8 1 3 6

1. Example 1:
1. Example 2:
1. Example 3:
1. Example 4:
Β
Β

#### Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB