Need help with following assignment written in C code:

This assignment deals with binary search trees (BSTs). Youll create a program that lets a user enter data, and builds a BST from that data. Your program will also let the user interact with that BST, using a series of commands:

• s number this will search for number in the BST. Tell the user whether that number is found or not.
• d number search for number and, if found, delete it. If it is not found, tell the user.
• X this command is used to display information about the BST. The following information should be displayed:
  • pre-, in- and post-order traversal of the tree. For each one, output the string NLR LNR: or LRN: followed by a commaseparated list of the nodes. Output one line for each traversal.
  • output data from a breatdh-first traversal of the tree: Output the string BFS: followed by a comma-separated list of the nodes.
  • output the height of the tree (an empty tree has height -1; a tree with a single node has height 0; etc.) Your output should say HEIGHT: followed by the height.
  • Indicate whether or not the tree is balanced. Your output should say BALANCED: followed by YES or NO
• ? display a help message giving the user a list of valid commands.
• Q exit the program

If only a number is entered (positive, negative, or 0), insert it into the tree. Only allow a number to be entered once. If the user tries to insert a number thats already in the tree, you should print an error message and not insert the second copy of the number.

Typing anything else should print an error message, and tell the user how to get help.

1. Details

Do not balance the tree! Insert nodes only below leafs, in the unique location that preserves the property of being a BST. When deleting a node N, select the largest node from Ns left sub-tree to replace N, unless there is no left sub-tree; in that case, move the root to point to Ns right sub-tree.

Be sure to free all memory that you allocate.

You should code your insert, search, delete, height, balance-check and depthfirst-search routines recursively. Your breadth-first search should be implemented using a queue.

2. Suggestions

I suggest writing your insert and in-order traversal code first. This lets you make a main program that simply calls your insert code with fixed values, which should build a tree. Then you can call your traversal code to confirm that your insertion works correctly. Once that is working, deletion is the next major hurdle.

Make your code modular, and use simpler pieces to help you in writing the more complex parts of your code.