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.

Academic Honesty!
It is not our intention to break the school's academic policy. Projects posted are only used as a reference and should not be submitted as is. We are not held liable for any misuse of the solutions. Please see the frequently asked questions page for further questions and inquiries.
Kindly fill out the form. Please provide a valid email address and we'll get back to you in less than 24 hours. We will be sending an invoice through PayPal upon confirmation. We are a non profit organization however we need an amount to keep this organization running, and to be able to complete our research and development.