Write a binary search tree class (called Bst) that contains C++ string objects. A binary search tree (BST), is a binary tree (up to two children per node) where for every node in the tree, all the values in the node's left subtree are less than the nodes value and all the values in the nodes right subtree are greater than (or equal to) 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.
All program input/output must be done in main.cpp. This means that the Bst class methods must pass results back to the caller using return values and/or reference parameters. Use an STL vector when you need to pass multiple strings into or out of a method.
Your program must handle the commands listed in the table below. If a command has an argument, the argument will be on the same line as the command. String arguments are allowed to contains spaces (so you will need to use getline() to read arguments).
Each line of the input will have the following format (you may assume that there is always a space between the command and the argument). The "<" and > are NOT in the input.
If there is no argument:
< command>< newline>
If there is an argument:
< command>< space>< string that may contain spaces>< newline>
The space following the command is NOT part of the string.
Assume that all string arguments are NOT empty.
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
< Monday> is in tree.
< Sunday> 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.
| Command | Argument | Action | Potential Error |
| echo | string | Write the string to standard output. Do not insert into tree. Used for commenting tests. Has nothing to do with the tree | none |
| insert | string | Insert the given string into the binary search tree. The tree must maintain the BST property after insert. | Print error if string already in tree. |
| size | none | Print the number of nodes in the tree. | none (Output 0 if tree is empty) |
| find | string | Output if the given string is or is not in the tree (both messages to stdout) | none |
| none | Use a depth-first traversal (dft) to print all elements in the tree. | none (empty brackets if tree is empty) | |
| breadth | none | Use a breadth-first traversal (bft) to print all elements in the tree. | none (empty brackets if tree is empty) |
| distance | none | Print the average distance nodes are from the root. The roots distance is 0. The roots children are distance == 1, the roots grandchildren are distance == 2, and so on. Calculate the distance for ALL nodes and then take the average. | none (0 if zero or one nodes) |
| balanced | none | Print if the tree is balanced or not balanced (this type of balanced is called height-balanced. | none (balanced if empty) |
| rebalance | none | Modify the tree so it is balanced. |
| Command | Output Formatting |
| echo | Print string argument to standard output followed by newline. |
| insert | None unless there is an error (see below for error message). |
| size | Print the integer size of the tree to standard output followed by a newline. |
| find | If the target string is in the tree, print the following to standardoutput: "str is in tree.\\n" where str is the target. |
| Traverse the tree using an in-order depth-first algorithm. Print all the elements inside of curly-braces {}, separate strings by a comma+space, and terminate with a newline. {string one, string two, string three} There is NO comma after the last string. Print "{}\\n" if the tree is empty (no space between the braces). | |
| breadth | Traverse the tree using a depth-first algorithm. Use the same output format as for the 'print' command. |
| distance | Print "Average distance of nodes to root = " followed by the average (as a double) of all the node's distances from root followed by a newline. |
| balanced | If the tree is balanced, output to standard output: "Tree is balanced.\\n" |
| rebalance | none |
If an illegal command is entered, print to standard error: "Illegal command < cmd>.\\n" where < cmd> is the illegal command. After an illegal command is entered, skip all other characters on that line of input and continue the program.
If insert is called on a string that is already in the tree, print to standard error: "insert < str> failed. String already in tree.\\n" where < str> is the string entered.
The program should continue after both types of errors.
NOTE: RETURN 0 FROM MAIN FOR THIS PROJECT, EVEN IF ERRORS WERE DETECTED IN THE INPUT.
Note: String arguments may contains spaces, so you must read them using getline(). You should always call cin.ignore() when switching from using the >> operator to using getline().
Note: Commands do not contain spaces, so you can read them using operator>> (e.g. while (cin >> command)).
1. Free all dynamically allocated (heap) memory prior to program exit.
2. Avoid code duplication.
3. Use a single return statement for all functions & methods that return a value.
4. Follow our standard variable naming rules: Local variables are all lowercase, with underbars between words, e.g. my_array. Class member variables begin with m_ and are all lowercase, with underbars between words, e.g. m_count. Class names and Struct names are "camel case", starting with an uppercase letter, e.g. IntStack. Constants are ALL CAPS.
5. Use descriptive names for all classes, structs, functions, methods, parameters, variables and types.
6. Do not declare any non-constant global variables.