Merge two price trees

Problem

Two binary search trees hold prices. Print all keys of both trees in increasing order, separated by spaces. A key that is in both trees is printed twice.

Input, output and limits

Input: Line 1: the first tree in level order, keys separated by spaces, with # for a missing child. Line 2: the second tree in the same format. A single # is an empty tree. The children of a missing node are not listed.
Output: The merged keys in increasing order.
Constraints: 0 ≤ nodes in each tree ≤ 300, at least one tree is not empty
1 ≤ each key ≤ 1000000

Examples

Example 1

Input

2 1 3
5 4 6

Output

1 2 3 4 5 6

Example 2

Input

#
7

Output

Hints

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

Hint 1

Each inorder walk is already sorted.

Hint 2

heapq.merge combines sorted streams without sorting again.

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

Solve in the editor

Count the BST shapeshard
Largest valid price tree insidehard
Greater sum treehard
Two orders that add upmedium
Orders in a number rangemedium

All Python problems

Problem

Input, output and limits

Examples

Hints

More Binary Search Trees problems

Problem

Input, output and limits

Examples

Hints

More Binary Search Trees problems