In this problem, you are to implement a binary search tree
with insert, traverse, delete operation.
The rules of delete is as follows:
(1) If deleting a node X without any children (i.e., deleting a leaf),
the new tree will simply remove X.
(2) If deleting a node X with exactly 1 child C,
(i) If X is the root, simply remove X and make C the root of the new tree.
(ii) Else, simply remove X and connect parent of X to C in the new tree.
(3) Else, we delete a node X with 2 children.
Then, swap X with the successor, and then delete X (similar to the
description in the lecture notes).
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 100000).
Each operation occupies a line.
"Insert X" means to insert X (number) into the BST.
"Delete X" means to delete X from BST, if X does not exist in the BST then nothing should be done.
"Traverse" means to traverse the BST in preorder.
All numbers are positive and not greater than 100000.
No duplicated number will be inserted into BST.
Assume the BST is empty at initial.
For "Traverse" operation, output a line contains your traverse progress in the BST and seperate each
number with a space.
If the BST is empty, you should still output an empty line.