Create a Binary Search Tree,

which supports the following operations. · insert(tree, element) - adds the node specified by element (which contains the data) into the BST specified by tree.

· search(tree, key) - searches for the data specified by key in the BST specified by tree.

· findMin(tree) - retrieves the smallest data in the BST specified by tree. · findMax(tree) - retrieves the largest data in the BST specified by tree. · predecessor(tree, element) - retrieves the inorder-predecessor of the node specified by element in the BST specified by tree. · successor(tree, element) - retrieves the inorder-successor of the node specified by element in the BST specified by tree.

· delete(tree, element) - removes the node specified by element from the BST specified by tree. Input - Output Format The input consists of multiple lines, each one containing either one or two integers. The first integer in the line can be 0, 1, 2, 3, 4, 5, 6, or 7 and each one has its own meaning: · The integer 0 means stop the program.

· The integer 1 means, create a node which contains the next integer from the input as the data part, and then, insert this node into the BST. In this case, the next integer (>= 0) is given on the same line as the 1, separated by a space. CS2094 - Data Structures Laboratory Page 3/7

· The integer 2 means, search for the key specified by the next integer from the input, in the BST. In this case, the next integer (>= 0) is given on the same line as the 2, separated by a space. If the search is successful, output "FOUND". Otherwise, output "NOT FOUND".

· The integer 3 means find and output the minimum number in the BST. Print "NIL" if the BST is empty.

· The integer 4 means find and output the maximum number in the BST. Print "NIL" if the BST is empty.

· The integer 5 means find and output the inorder-predecessor of the data specified by the next integer from the input. In this case, the next integer (>= 0) is given on the same line as the 5, separated by a space. Output "NIL", if the data exists in the tree, but there is no inorder-predecessor for the data. Output "NOT FOUND", if the data is not present in the tree. · The integer 6 means find and output the inorder-successor of the data specified by the next integer from the input. In this case, the next integer (>= 0) is given on the same line as the 6, separated by a space. Output "NIL", if the data exists in the tree, but there is no inorder-successor for the data. Output "NOT FOUND", if the data is not present in the tree. · The integer 7 means delete the data specified by the next integer in the input from the BST, if present. In this case, the next integer (>= 0) is given.