Assume that you are manager in Panera restaurant. Your restaurant offers some number of sandwiches. You want to keep track of what is ordered and is served yet.

So you need to count the frequencies of sandwichesthat are ordered and what is served .

For simplicity, consider that your restaurant offers 10 different sandwiches:

1 - Cuban

2 - Heritage Ham & Swiss

3 Steak & Arugula

4 Modern Caprese

5 Steak & White Cheddar Panini

6 BBQ Chicken Flatbread

7 The Italian

8 Frontega Chicken Panini

9 BBQ Chicken Flatbread

10 Bacon Turlkey Bravo

Write a program that allow to increase counter of sandwich by one for each sandwich that is ordered and reduce counter for the sandwich that is alredy served.

Programming Guidelines:

Use Node to store

number_of_sandwich (int)

counter - to store number of ordered sandwishes, but not served yet(int)

title of sandwich (string)

Use a binary search tree to store the information about sandwiches.

Use inorder binary tree traversal to output all current information in the increasing order (on number_of_sandwiches).

You will need insert Node in binary search tree and delete Node from binary search tree.

When you insert Node that is not in the tree, you add it in proper place,

When you insert Node that is already in the tree, you actually increase counter of this Node by 1.

When you delete Node that is not in the tree, you print error, it is not possible to serve

sandwich that was not ordered.

When you delete Node that is in the tree and counter is greater than 1, you reduce counter by 1 - sandwish is served.

When you delete Node that is in the tree and counter is equal 1, you delete the Node from tree - sandwich is served and no more waiting to be served of this kind.

The following definition for the binary search tree modifies the node class to hold the two values:

struct Sandwich{

int sandwichNumber;

int counter;

string sandwichTitle;

};

typedef Sandwich Element;

struct Node

{

Element data;

Node* leftchild;

Node* rightchild;

};

class BinarySearchTree

{

public:

BinarySearchTree();

bool isEmpty(); // return true if the tree is empty, otherwise return false

void insert(int sandwichNum); //insert a value sandwichNum

Node* find (int sandwichNum); //return pointer on Node with sandwichNum number

bool isFound (int sandwichNum);//return true if sandwichNum is in the tree, otherwise return false

void Display(); //Display the data stored from smallest to largest based on sandwich number

void remove(int sandwichNum); // see above about removing : either remove Node with sandwichNum number

// or print error message, if there is no Node in the tree with this number

// or reduce counter by one in the Node with this sandwichNum

private:

Node * root;//pointer to the root node

//add necessary private functions that serves your needs

};

Ordered:

Sample input inserts: 3 3 4 1 5 6 7 7 9 7 10 1 2 2

Sample output:

Currently ordered and not served yet:

1 - Cuban 2 orders

2 - Heritage Ham & Swiss 2 orders

3 Steak & Arugula 2 orders

4 Modern Caprese 1 order

5 Steak & White Cheddar Panini 1 order

6 BBQ Chicken Flatbread 1 order

7 The Italian 3 orders

9 BBQ Chicken Flatbread 1 order

10 Bacon Turlkey Bravo 1 order

After serving

Sample input removes: 3 4 1 5 8 2

Currently ordered and not served yet:

1 - Cuban 1 orders

2 - Heritage Ham & Swiss 1 orders

3 Steak & Arugula 1 orders

8 Frontega Chicken Panini is not ordered

6 BBQ Chicken Flatbread 1 order

7 The Italian 3 orders

9 BBQ Chicken Flatbread 1 order

10 Bacon Turlkey Bravo 1 order

PS. If you try to insert or remove Node with sandwichNumber that is not from our list, simply print error message: InvalidSandwichNumber.