1. Write a C++ program that creates a binary search tree, empirically calculates the average search cost for each node in such a tree, and removes a designated node. Your program should: Read integer data from the le designated by the user. Every line of the le contains one input integer. Assume that each integer in the input data le is unique. (Note that there is no number that gives the total number of integers in the le)

Print the input data on the screen.

Create a binary search tree based on the input data. Calculate the search cost for each node when it is inserted and store it in a tree node. A binary node element has at least two data elds: Key and SearchCost For each node, count and store the number of comparisons required when searching for the node (i.e., the number of comparisons = the search cost for the node = 1+ the depth of the node)

Print the binary search tree by performing all three traversal operations: If the number of nodes is less than 24, print on the screen the resulting tree along with the information about the nodes (for each node, print both its key and search cost). Otherwise, print this tree and information about its nodes into a le. See the example below.

Print the binary search tree level-by-level: If number of nodes is less than or equal to 24, print the tree level-by-level to a le. For trees larger than 24, you do not need to output it as the le may be large. See the experiment section.

Remove a node designated by a user from the binary search tree and print the resulting tree on the screen if the number of nodes is less than 24. You should update the search costs of the tree nodes if the costs have been changed upon node removal.

Calculate the average search cost for all nodes in the tree and print it. Sum up the search cost over all the nodes in your tree as you traverse the tree in one of three traversals. Divide the sum by the total number of nodes in the tree, and the result is the average search cost for all the tree nodes

Print total number of nodes