Description

Please implement a binary search tree (BST) with four basic operations, which are "insert", "inorder", "delete", and "search".

You may use the code template below and replace /*TODO*/ section with your code.

Template.cpp

<removed>

Input

The inputs are constructed as follows:

• insert i: Insert the integer i into the BST.

• delete i: Delete the integer i from the BST.

• inorder: Print the inorder traversal representation of the BST.

• postorder: Print the postorder traversal representation of the BST.

• search i: Print True if the integer i is in the BST, otherwise, return False.

Note:

• The integers would not be repeated in the inputs.

• There would be no illegal inputs. (For example, delete i while i is not in the BST)

Output

The corresponding outputs should be constructed as follows:

• For inorder and postorder, print the integers separated by new line characters.

• Print Found to search i if the integer i is in the BST.

• Print Not found to search i if the integer i is not in the BST.

Note: You should append a newline character(\n) after each output.

Sample Input  Download

Sample Output  Download

Tags

Discuss