Write a program in C$++$ to create a Binary Search tree $($BST$)$ of integers. The program will perform these operations: Insert node$($s$),$ Traverse Post$-$order, Search node, Delete node, Leaf Count, Children of a node and Quit.

Use the header file like this:

#include

#ifndef BT$\_$H

#define BT$\_$H

using namespace std;

class BT

$\{$

private:

struct node

$\{$

int data;

node$*$ left;

node$*$ right;

$\}$;

node$*$ root;

public:

BT$()$; $//$Constructor

bool isEmpty$()$ const $\{$ return root $==$ NULL; $\}//$Check for empty

void insert$($int$)$; $//$Insert item in BST

void print$\_$postorder$()$; $//$In$-$order traversing driver

void postorderTrav$($node$*)$; $//$In$-$order traversing

void searchBST$($int$)$; $//$Searches BST for a specific node

void deleteNode$($int$)$; $//$Delete item from BST

int count$()$; $//$Count driver

int leafCount$($node$*)$; $//$Counts number of leaves in BST

void nodeChildren$($int$)$; $//$Finds children of a node

$\}$;

#endif

Use the following menu in your program. Must place your name in the menu heading.

$--------------------$ MENU $($YOUR NAME$)----------------$

$1.$ Insert node$($s$)$

$2.$ Traverse Post$-$order

$3.$ Search node

$4.$ Delete node

$5.$ Leaf Count

$6.$ Children of a node

$7.$ Quit

Enter your choice: $\_\_$

Use the following characters in the given order to form the BST tree:

$2010153025400535$

$($Hints: $1.$ Before you start working on the program, you draw the BST for the given order of the above numbers. It will help you check your output for the options in the menu. $2.$ While working on the program, test with few items $-$ such as $20101530,3.$ You work on one menu at a time then it will be easier to test and manage the program instead of writing the whole program for entire menu then test your program.$)$

Option $1$: Inserts node$($s$)$ in a BST$.$

Enter Your Choice $<1-7>1$

Enter number of items to insert: $4$

Enter node: $20$

Inserted.

Enter node: $10$

Inserted.

Enter node: $15$

Inserted.

Enter node: $30$

Inserted.

Option $2$: Traverse the tree in Post$-$order and display the node info and its left child info and right child info. If a node does not have a child, then display NIL.

Enter Your Choice $<1-7>2$

Sample output:

Traversing Post$-$order

Node Info Left Child Info Right Child Info

$------------------------------------------$

$15$ NIL NIL

$10$ NIL $15$

$30$ NIL NIL

$201030$

Option $3$: Search for the item in the BST$.$

It will prompt: Enter item you want to search for: $10$

If the item is found, then display the message $\_\_\_$ is found in the BST$.$ If the item is not found then it will display $\_\_\_\_$ is not found in the BST$$

$10$ is found in the BST

Option $4$: Deletes a node from the BST$.$

It will prompt: Enter item you want to delete: $30$

If the item is found then delete the item from the BST and displays the message $\_\_\_$ is deleted$$ If the item is not in the BST$,$ then it will display $\_\_\_\_$ is not found in the BST$$

$30$ is deleted

Option $5$: Counts the number of leaves in the BST and displays $$

$$There are $\_\_\_\_$ number of leaves in the BST$$

There are $2$ number of leaves in the BST

Option $6$: Enter the item and it will display the children of that item.

It will prompt: Enter the item you want to display the children of:

Left child: $\_\_\_$

Right child: $\_\_\_$

If the item has no children, then it displays:

$\_\_\_\_$ has no children.

Ex: Enter the item you want to display the children of: $10$

Left child: NIL

Right child: $15$

Option $7$: Quit the program.