Operations on Binary Search Trees

You are given several operations to perform on Binary Search Trees (BST). The operations include performing an inorder traversal, converting a sorted list into a balanced BST, balancing an unbalanced BST, printing the inorder traversal of a BST, and merging two BSTs into one balanced BST. The BST operations should be implemented such that the inorder traversal of a BST always produces a sorted list. In addition, when merging two BSTs, all the values are combined and then a balanced BST is constructed.

Operations:

• 1: Inorder Traversal. Input a serialized BST in level order (use the token null to represent missing nodes), and output its inorder traversal.
• 2: Sorted List to BST. Given a sorted list of integers, build a balanced BST and output its inorder traversal.
• 3: Balance BST. Given a serialized (possibly unbalanced) BST, balance it and output its inorder traversal.
• 4: Print Inorder. Given a serialized BST, simply print its inorder traversal (values separated by a single space) followed by a newline.
• 5: Merge Two BSTs. Given two serialized BSTs, merge them into one balanced BST and output its inorder traversal.

Note: For any operation, the output should present the inorder traversal as a sequence of integers separated by a single space, ending with a newline.

All formulas (if any) should be written in LaTeX format. For example, the height of a BST might be denoted as \(h=\lceil\log_2(n+1)\rceil\).

inputFormat

The input starts with an integer op denoting the operation to perform:
1: Inorder Traversal
2: Sorted List to BST
3: Balance BST
4: Print Inorder
5: Merge Two BSTs

The subsequent input lines depend on op:

• If op is 1, 3, or 4: The next line contains a serialized BST given in level order, with nodes separated by spaces. Use the token null to represent missing nodes.
• If op is 2: The next line contains an integer n representing the number of sorted integers, followed by a line with n space-separated integers.
• If op is 5: The next two lines each contain a serialized BST (in level order, space separated, with null for missing nodes).

outputFormat

Print the inorder traversal of the resulting BST. The output should be the list of integers separated by a single space and terminated with a newline character.

## sample

1
3 1 4 null 2

1 2 3 4

</p>