[50%]
In this problem, you need to implement a BST with following operations :
1. Insert x : Insert x into BST
2. Traverse : Print the preorder traversal order of the BST in one line, each number is separated by a space. If BST is empty, outputs "empty" instead.
3. Bigger x : Given x, output the smallest number which is bigger than x in BST. (x always esxists in BST). If the number doesn't exist, outputs "none" instead.
4. Smaller x : Given x, output the largest number which is smaller than x in BST. (x always exists in BST) If the number doesn't exist, outputs "none" instead.
There are only one test case, and the input will terminate with an EOF.
In the test case, there will be several operations (no more than 10000).
Each operation occupies a line, which is one of the four operations described in the problem statement.
All numbers are positive and not greater than 1000000000.
No duplicated number will be inserted into BST.
Assume the BST is empty at initial.
For "Traverse", "Smaller x", "Bigger x" operation, outputs one line.
The content is described in the problem description.