*** NEED THE CODE IN C LANGUAGE***

#include  #include  struct Node { char val; struct Node * left; struct Node * right; }; void display_tree(struct Node * root); struct Node * insert(struct Node * root, char val); struct Node * destroy_tree(struct Node * root); struct Node * create_tree(struct Node * root); struct Node * search(struct Node * root, char val); void inorder(struct Node * root); struct Node * pred_tree(struct Node * root, char val); void main() { struct Node * root = create_tree(root); printf("Initial tree: "); display_tree(root); printf("List of nodes in order: "); inorder(root); printf(" "); char key='k'; printf("Predecessor of %c: ", key); struct Node * key_ptr = pred_tree(root,key); if (key_ptr == NULL) printf("NULL "); else printf("%c ",key_ptr->val); key='r'; printf("Predecessor of %c: ", key); key_ptr = pred_tree(root,key); if (key_ptr == NULL) printf("NULL "); else printf("%c ",key_ptr->val); key='q'; printf("Predecessor of %c: ", key); key_ptr = pred_tree(root,key); if (key_ptr == NULL) printf("NULL "); else printf("%c ",key_ptr->val); key='o'; printf("Predecessor of %c: ", key); key_ptr = pred_tree(root,key); if (key_ptr == NULL) printf("NULL "); else printf("%c ",key_ptr->val); destroy_tree(root); } struct Node * pred_tree(struct Node * root, char val) { return NULL; } void destroy_node(struct Node * root) { if (root != NULL) free(root); return; } struct Node * search(struct Node * root, char val) { if (root == NULL) return NULL; if (root->val == val) { return root; } if (val val) { return root->left; } else { return root->right; } } struct Node * create_node(char val) { struct Node * p = (struct Node *) malloc(sizeof(struct Node)); p->val = val; p->left = NULL; p->right = NULL; return p; } struct Node * create_tree(struct Node * root) { struct Node * p = NULL; p = insert(p,'k'); p = insert(p,'b'); p = insert(p,'a'); p = insert(p,'f'); p = insert(p,'d'); p = insert(p,'c'); p = insert(p,'e'); p = insert(p,'r'); p = insert(p,'n'); p = insert(p,'m'); p = insert(p,'p'); p = insert(p,'s'); p = insert(p,'z'); p = insert(p,'o'); p = insert(p,'q'); return p; } struct Node * destroy_tree(struct Node * root) { if (root == NULL) return NULL; destroy_tree(root->left); destroy_tree(root->right); return NULL; } struct Node * insert(struct Node * root, char val) { if (root==NULL) { return create_node(val); } if (val == root->val) { printf("Insertion failed: '%c' is already in the tree ", val); } else if (val val) { root->left = insert(root->left, val); } else { root->right = insert(root->right, val); } return root; } char display_val(struct Node * root) { if (root==NULL) return '/'; else return root->val; } void display_tree(struct Node * root) { if (root==NULL) return; printf("%c -> %c, %c ",root->val,display_val(root->left),display_val(root->right)); display_tree(root->left); display_tree(root->right); return; } void inorder(struct Node * root) { if (root == NULL) return; inorder(root->left); printf("%c ", root->val); inorder(root->right); return; } 

Problem 3 [1 pt]. Attached is a program pred_tree.c which has a function struct node * pred_tree(struct node * root, char val) that returns the predecessor of val, and more accurately, the pointer to the node of the predecessor. If val is not in the tree then the function returns NULL. The program uses the following binary search tree for testing. Currently, the function pred_tree( ) is empty. Complete the function so that it works, and upload the program The output should look like this: Initial tree: kb,rba,fa///fd,/dc,ec/,/e///rn,snm,pm/,/pd,qo>/,/q/,/s/,zz/,/ List of nodes in order: abcdefkmnpqrsz Predecessor of k:f Predecessor of r: q Predecessor of q:p Predecessor of o: n