Description

You are asked to implement a binary search tree. You have to implement the following methods.

1.  Insert x:

     Insert an integer x into the binary search tree if x is not in the tree yet. If x is NOT in the binary search tree, you don’t need to do anything.

2. Delete x:

     Delete x if x is in the binary search tree. Please use the smallest element in right subtree to replace x. If x is not in the binary search tree, you don’t need to do anything.

3. Height:

     Print the height of the binary search tree.

4. Find x:

     Print “Find x: Yes” if x is in the binary search tree; Otherwise, print “Find x: No”.

5. Clear:

     Drop all the nodes of the binary search tree.

 

Note:

1. Test Case 1: In this test case, there is no Delete operation.
2. Test Case 2: In this test case, only leaves would be deleted.
3. Each data element is an integer ranging from 1 to 99999.

Input

There are many lines in the input. Each line contains an operation defined above.

Output

For a “Find” or a “Height” operation, you need to output the result of the operation.

Sample Input  Download

Sample Output  Download

Tags

Add Tag

Discuss