Left Right binary Tree

Implement a binary search tree for integers using the Leftmost-Child Right-Sibling representation. You will need to create a class to represent a single node. Then you will need an additional class to represent all of the tree structure. Within that class you must implement methods to insert nodes, obtain the current height of the tree, search for a node and print the current contents in preorder. You are not allowed to use the C++ standard template library.

Once the program is started, it will print out the promt "LCRS> " (> is followed by a whitespace):

./a.out LCRS>

You will implement the commands "insert", "height", "search", "preorder" and "quit":

insert

Insert takes as an argument the number that will be inserted into the tree. Insert it into the tree using the corresponding function in your tree class. If an element already exists, do nothing. Then repeat the prompt.

LCRS> insert 5
LCRS> insert 25
LCRS> insert 35
LCRS>

height

Height does not take any arguments. Compute the height of the tree using the corresponding function in yourt tree class. The result will be on a new line without the prompt prepended. Remember that the height of a tree containing only the root node is 0. Use -1 as the height of an empty tree. Then repeat the prompt.

LCRS> height
2
LCRS>

search

Search takes as an argument the number that is to be serached for. Print "true" or "false" depending on the outcome of the search using the corresponding function in your tree class. The result will be on a new line without the prompt prepended. Then repeat the prompt.

LCRS> search 20
true
LCRS> search 25
true
LCRS> search 12
false
LCRS>

preorder

Preorder does not take any arguments. Use the corresponding preorder function in your tree class. The result will be on a new line separating the elements by commas. Then repeat the prompt.

LCRS> preorder
20,10,5,30,25,35
LCRS>

quit

Exit the program

LCRS> quit

Error Handling

If the command received from the user input is not supported, print out an error message starting with "Error!". (Do not capitalize the entire word "Error") You can assume that the user only tries to insert numbers.