How would you program this in C

1.6 bst: Binary search trees Write a program bst that manipulates binary search trees. It will receive commands from standard input, and print resposes to those commands to standard output. 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 portion of the assignment has two parts. Part 1 In this part, you will implement bst with three commands: insert n Adds a value to the tree, if not already present. The new node will always be added as the child of an existing node, or as the root. No existing node will change or move as as result of inserting an item. If n was not present, and hence has been inserted, bst will print inserted. Otherwise, it will print not inserted. The instruction format is an i followed by a decimal 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. print Prints the current tree structure, using the format in section 1.6.1. Part 2 In this part, you will implement bst with an additional fourth command: delete n Removes a value from the tree. See section 1.6.2 for further discussion of deleting nodes. If n is not present, print absent. Otherwise, print deleted. The instruction format is a d followed by a space and an integer n. Input format The input will be a series of lines, each beginning with a command character (i, s, p, or d), possibly followed by a decimal integer. When the input ends, the program should terminate. Your program will not be tested with invalid input. A line that cannot be interpreted may be treated as the end of the input. Output format The output will be a series of lines, each in response to an input command. Most commands will respond with a word, aside from p. The format for printing is described in section 1.6.1. 5 3 6 4 Figure 1: A binary search tree containing six nodes Usage $ ./bst i 1 inserted i 2 inserted i 1 not inserted s 3 absent P (1(2)) D As with list, the D here indicates typing Control-D at the start of a line in order to signal the end of file. 1.6.1 Printing nodes An empty tree (that is, NULL) is printed as an empty string. A node is printed as a (, followed by the left sub-tree, the item for that node, the right subtree, and ), without spaces. For example, the output corresponding to fig. 1 is ((1)2((3(4) 5(6))). 1.6.2 Deleting nodes 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 2a shows the result of deleting 4 from the tree in fig. 1. If a node has one child, it can be replaced by that child. Figure 2b shows the result of deleting 3 from the tree in fig. 1. Note that node 4 is now the child of node 5. 7 2 2 1 5 1 5 3 6 4 6 (a) Deleted 4 (b) Deleted 3 2 1 4 3 6 (c) Deleted 5 Figure 2: The result of deleting different values from the tree in fig. 1 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 2c shows the result of deleting 5 from the tree in fig. 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