Write a menu driven program that will allow the user to add, delete, and print a binary tree. There should be two orders $($LNR and RNL$)$ for printing. Binary Tree:

A binary tree is either empty or consists of a single vertex and two disjoint subsets each

of which is also a binary tree.

Structure of a Binary Tree:int data;

struct treenode $*$left$,*$right;

$\}*$binarytree;Declaring a binary tree:

binarytree root;

Initialize a binary tree:

use pass by reference

set root to NULL

Checking for empty tree:

use pass by value

if root is NULL, then tree is empty

Checking for full tree:

use pass by value

can we allocate memory the size of a treenode structure?

Adding to a tree:

assuming tree is NOT full

use pass by reference

if current position is empty

allocate memory the size of a tree node structure

put data in it

set both left and right children to NULL

otherwise $($keep looking for empty spot$)$

if data to add is $$ current node's data

use recursive call to add to left subtree... add$($ &$(*t)->$left, datatoadd$)$

otherwise

use recursive call to add to right subtree assuming tree is NOT empty and user has specified data to be removedif not empty if no children set $(*$t$)$ to NULL if left child only move $(*$t$)$ to left child if right child only move $(*$t$)$ to right child if two children set temp to $(*$t$)->$ right move temp to left subtree move temp back to $(*$t$)$ free temp set temp to $(*$t$)->$left move temp to right subtree move temp back to $(*$t$)$ free temp if data we are looking for is current data otherwiseotherwise Printing the contents of the binary tree:

Assuming you've already checked to make sure the tree isn't empty or printed the

appropriate message in main, you will pass the tree using pass$-$by$-$value since no changes

will be made.

LNR $($Left$,$ Node, Right$)/$ Ascending Order

if the tree is not empty

call LNR recursively sending the left subtree

print the data portion of the current node

call LNR recursively sending the right subtree

RNL $($Right$,$ Node, Left$)/$ Descending Order

if the tree is not empty

call RNL recursively sending the right subtree

print the data portion of the current node

call RNL recursively sending the left subtree Testcase for Binary Tree:

Delete $-$ empty

LNR $-$ empty

RNL $-$ empty

Add $6$

Add $7$

Add $3$

Add $4$

Add $2$

LNR $-23467$

Delete $4-$ testing no children

LNR $-2367$

Add $5$

Add $8$

Add $7$

Delete $10-$ not found

Add $1$

Add $3$

Add $4$

Invalid Menu Option $-$ error message

Add $9$

Add $10$

LNR $-1233456778910$

Delete $5-$ testing left child only

$RNL-109877643321$

Delete $9-$ testing right child only

$LNR-12334677810$

Delete $6-$ two children

LNR $-1233477810$

Quit