The program must be written in C. Write a program bst that maintains and manipulates a binary search tree according to instrctions provided in a le. bst takes one argument, which is a path to a le containing the instructions. If the le does not exist, bst must print error and nothing else. A binary search tree is a binary tree that stores integer values in its interior nodes. The value for a particular node is greater than every value stored its left sub-tree and less than every value stored in its right sub-tree. The tree will not contain any value more than once. bst will need to allocate space for new nodes as they are created using malloc; any allocated space should be deallocated using free before bst terminates. This problem has three parts. For part one (9 points), you must implement two operations on the binary search tree: insert and search. For part two (6 points), you must implement one additional operation: print. For part three (9 points), you must implement a second additional operation: delete. The remaining 4 points are for style. All three parts are submitted as a single program. You will receive partial credit if your program correctly handles part one or parts one and two. Input format Each line of the input le contains an instruction. Each line begins with a letter indicating the type of instruction. If the letter is i (insert), s (search), or d (delete), it will be followed by a space and an integer, indicating the argument n. The letter p (print) will occur on a line by itself. If the input le does not exist, is not readable, or does not have the correct format, bst may print error. 1.8.1 Insertion and searching For part one, bst must implement two operations on binary search trees: insert n Adds a value n to the tree. The new node will always be added as a child of an existing node (or as the root if the tree is empty). No existing nodes in the tree will move or change values (that is, do not rebalance the tree). If n is already present, bst will print duplicate. Otherwise, it will print inserted. The instruction format is an i followed by a space and an integer n. search n Searches the tree for a value n. If n is present, bst will print present. Otherwise, it will print absent. The instruction format is an s followed by a space and an integer n. Usage Assume a text le file1.txt with the following content: i 10

i 8

s 5

i 5

i 10

s 5 With this assumption, $ ./bst file1.txt

inserted

inserted

absent

inserted

duplicate present 1.8.2 Printing For part two, bst must implement a third operation: print Prints the current tree structure according to the format described below. The instruction format is a p. Output format An empty tree (that is, a NULL pointer), is printed as an empty string (that is, nothing). A node is printed as a (, followed by the left tree, the value for the node, the right tree, and a ). For example, the output corresponding to Figure 1 is ((1)2((3(4))5(6))). Usage Assume a text le file2.txt with the following content: i 10

i 5

s 8

p

i 8

i 10

s 8

p

With this assumption, $ ./bst file2.txt

inserted

inserted

absent

((5)10)

inserted

duplicate

present

((5(8))10)

1.8.3 Deletion For part three, bst must implement a fourth operation: delete n Remove the value n from the tree. If n is not present, print absent. Otherwise, print deleted. The instruction format is a d followed by a space and an integer n. There are several strategies for deleting nodes in a binary tree. If a node has no children, it can simply be removed. That is, the pointer to it can be changed to a NULL pointer. Figure 2(a) shows the result of deleting 4 from the tree in Figure 1. If a node has one child, it can be replaced by that child. Figure 2(b) shows the result of deleting 3 from the tree in Figure 1. Note that node 4 is now the child of node 5.If a node has two children, its value will be changed to the maximum element in its left subtree. The node which previously contained that value will then be deleted. Figure 2(c) shows the result of deleting 5 from the tree in Figure 1. Note that the node that previously held 5 has been relabeled 4, and that the previous node 4 has been deleted. Note that the value being deleted may be on the root node. Usage Assume a text le file3.txt with the following content: i 10

i 5

s 8

p

i 8

d 6

p

d 5

p With this assumption, $ ./bst file3.txt

inserted

inserted

absent

((5)10)

inserted

absent

((5(8))10)

deleted

((8)10)