(Solved): Please help for DSA! Thank you!! Write a program in C++ to create a Binary Search tree (BST) of int ...

Please help for DSA! Thank you!!

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: 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: \begin{tabular}{lllllllll} \hline 20 & 10 & 15 & 30 & 25 & 40 & 0 & 5 & 35 \end{tabular} (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: 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: \( \quad \) Quit the program.