Prices in sorted order

Problem

Print all keys of a binary search tree from smallest to largest, separated by spaces.

Input: Line 1: the tree in level order, keys separated by spaces, with # for a missing child. The children of a missing node are not listed, and trailing # may be left out. A single # is an empty tree.
Output: The keys in increasing order on one line.
Constraints: 1 ≤ number of nodes ≤ 300
1 ≤ each key ≤ 1000000, all different

Example 1

Input

8 3 10 1 6 # 14 # # 4 7 13

Output

1 3 4 6 7 8 10 13 14

Example 2

Input

2 1 3

Output

1 2 3

Try the problem first. Open one hint at a time.

Hint 1

Visit the left subtree, then the node, then the right subtree.

Hint 2

A generator with yield from keeps it short.

Write your Python code, run it on the examples and submit it to hidden tests.