Reorder Leaves in a Binary Tree

You are given a binary tree in level order form. Your task is to reorder the leaf nodes (nodes with no children) so that their values become sorted in increasing order. The non‐leaf nodes should remain unchanged. After the reordering operation, output the in-order traversal of the modified tree.

The input is given as a single line representing the level order traversal of the tree. Nodes are separated by a single space and the string null represents a missing node.

Note: When reassigning the values, traverse the tree to find leaf nodes in the order (left subtree then right subtree) and replace each leaf’s value with the corresponding sorted value.

Example 1:

Input:  5 3 8 1 4 7 9
Output: 1 3 4 5 7 8 9

Example 2:

Input:  10 5 15 2 7 null 20
Output: 2 5 7 10 15 20

inputFormat

The input consists of a single line containing the level order representation of a binary tree. Nodes are separated by spaces and missing nodes are indicated by the string null. For example:

10 5 15 2 7 null 20

outputFormat

Output the in-order traversal of the binary tree after reordering its leaves. The values should be printed in a single line separated by a single space.

## sample

5 3 8 1 4 7 9

1 3 4 5 7 8 9