Need help with this program

Overview

Write a binary search tree class (called BST) that is a tree of C++ strings. A binary search tree (BST), is a binary tree (two children) where for every node in the tree, all the values in the nodes left subtree are less than the nodes value and all the values in the nodes right subtree are greater than the nodes value. Write a main.cpp that instantiates a BST object and reads and executes commands from standard input. See table below for the list of commands. Several of these commands are difficult to implement (especially the balanced and rebalance commands). It may take you a long time to figure out how to implement them.

1 Program Requirements All program input/output must be done in main.cpp. This means that the BST functions must pass results back to the calling function using return values and/or reference parameters. Use a Standard Template Library (STL) vector when you need to pass multiple strings. The program must handle the commands listed in the table below. If a command has an argument, the argument is on the same line as the command. All string arguments are allowed to contains spaces. Each line of the input will have the following format (assume there is always a space between the command and the argument). The are NOT in the input. If there is no argument: If there is an argument: The space following the command is NOT part of the string. Assume that all string arguments are NOT empty.

Sample Input/Output :

Input :

insert Saturday insert Friday insert Tuesday insert Monday insert Thursday insert Wednesday echo Number of nodes in tree: size find Monday find Sunday echo The nodes in depth-first order: print echo The nodes in breadth-first order: breadth balanced

Output:

Number of nodes in tree: 6 is in tree. is not in tree. The nodes in depth-first order: {Friday, Monday, Saturday, Thursday, Tuesday, Wednesday} The nodes in breadth-first order: {Saturday, Friday, Tuesday, Monday, Thursday, Wednesday} Tree is balanced.

2

3 Output Formatting

Command Argument Action Potential Error Write the string to standard output. Do not insert into tree. Used for commenting tests. Has nothing to do with the tree echo string none Insert the given string into the binary Print error if search tree. The tree must maintain string already in the BST property after insert insert string tree Print the number of elements (also none (0 if tree is number of nodes) in the tree size none empty Print if the given string is or is not in the tree (both messages to stdout) find string none Use a depth-first traversal (dft) to none(empty print all elements in the tree print none brackets if tree is empty) Use a breadth-first traversal (bft) to none print all elements in the tree breadth (empty none brackets if tree is empty Print the average distance nodes are none (0 if zero or from the root. The root's distance is one nodes 0. The root's children are distance distance one 1, the root's grandchildren are distance-= 2, and so on. Calculate the distance for ALL nodes and then take the average. Print if the tree is balanced or not none (balanced if balanced (this type of balanced is empty) called "height-balanced". balanced none rebalance none Modify the tree so it is balanced