This program performs basic operations on a binary search tree.

It reads a sequence of instructions from the standard input stream

and outputs the results to the standard output stream.

The program accepts the following instructions:

- `a value` and the `value` to the tree

- `s` remove the smallest value stored in the current tree (should have no effect

if the current tree is empty)

- `l` remove the largest value stored in the current tree (should have no effect

if the current tree is empty)

- `p` print the values stored in the current tree in order of the inorder traversal

The `main` function in `problem1.c` reads and parses the input stream and calls

appropriate functions to perform the instructions. __Your task is to implement

those functions so that the output produced is correct.__

__Example__

__Input:__

```

a park

a snow

a zoo

a car

a dinner

p

s

l

p

a crab

a rank

a herb

a rabbit

a sand

p

l

s

p

s

s

l

l

p

l

s

p

s

p

```

__Output:__

```

car dinner park snow zoo

dinner park snow

crab dinner herb park rabbit rank sand snow

dinner herb park rabbit rank sand

park rabbit

```

(notice that the last two lines of the output are blanks!).

__Deliverables:__

Implementation of the functions in `bst.c` file. You may add

declarations to the file `bst.h` (you have to upload the modified

file if you do so).

------------------------

bst.h file

#include

#include

#include

#include "bst.h"

void add ( bst_node ** root, char * word ) {

}

void inorder ( bst_node * root ) {

}

char * removeSmallest (bst_node ** root ){

return NULL;

}

char * removeLargest (bst_node ** root ){

return NULL;

}

problem1.c file

---------------------------------

#include

#include

#include

#include "bst.h"

int main() {

bst_node * root = NULL;

char * instruction = (char*) malloc(256*sizeof(char) ) ;

char * word = NULL;

while ( scanf("%s", instruction) > 0 ) {

//printf ( "read: %c ", instruction);

if ( strncmp(instruction,"a", 2) == 0 ) {

//add a value to the tree

word = (char*) malloc (256 * sizeof(char) );

scanf("%s ", word);

add(&root, word);

}

else if ( strncmp(instruction,"s", 2) == 0 ) {

//remove the smallest value in the tree

word = removeSmallest( &root);

//free memory that was allocated for the word

if (word != NULL) {

free(word);

word = NULL;

}

}

else if ( strncmp(instruction,"l", 2) == 0 ){

//remove the largest value in the tree

word = removeLargest( &root);

//free memory that was allocated for the word

if (word != NULL) {

free(word);

word = NULL;

}

}

else if ( strncmp(instruction,"p", 2) == 0 ){

//print the content of the tree in the inorder traversal

inorder ( root );

printf ( " ");

}

else {

printf ("Error: %s is not a valid instruction ", instruction);

}

}

if (word != NULL) {

free(word);

word = NULL;

}

if (instruction != NULL) {

free(instruction);

instruction = NULL;

}

return 0;

}