#include<iostream>

using namespace std;

struct Node
{
    int key;
    string name;
    double balanceDue;
    Node *left;
    Node *right;
};

Node *addNode(int key, string name, double balanceDue)
{
    Node *v = new Node();
    v-> key = key;
    v-> name = name;
    v-> balanceDue = balanceDue;
    v-> left = v-> right = NULL;
    return v;
}

Node *insert(Node *root, int key, string name, double balanceDue)
{
    if(root == NULL)
        root = addNode(key, name, balanceDue);
    else if(key <= root-> key)
        root-> left = insert(root-> left, key, name, balanceDue);
    else
        root-> right = insert(root-> right, key, name, balanceDue);
    return root;
}

bool search(Node *root, int key)
{
    if(root == NULL)
        return false;
    else if(root-> key == key)
        return true;
    else if(key <= root-> key)
        return search(root-> left, key);
    else
        return search(root-> right, key);
}

void inorder(Node *root)
{
    if(root == NULL)
        return;
    inorder(root-> left);
    cout << root-> key << " " << root-> name << " " << root-> balanceDue << endl;
    inorder(root-> right);
}

int main()
{
    Node *root = NULL;
    int num;
    string who;
    double amount;
    char again;
    
    cout << "Please enter the following information." << endl;  // get input
    cout << "Key (any nonnegative integer value used to identify the data): ";
    cin >> num;
    cout << "Individual's last Name: ";
    cin >> who;
    cout << "Balance Due on Account: ";
    cin >> amount;
    root = insert(root, num, who, amount);
    
    cout << "Do you want to add another individual (Y/N): ";    // adds as many as needed
    cin >> again;
    while (again == 'Y' || again == 'y')
    {
        cout << "Please enter the following information." << endl;  // get input
        cout << "Key (any nonnegative integer value used to identify the data): ";
        cin >> num;
        cout << "Individual's last Name: ";
        cin >> who;
        cout << "Balance Due on Account: ";
        cin >> amount;
        insert(root, num, who, amount);
        cout << "Do you want to add another individual (Y/N): ";    // adds as many as needed
        cin >> again;
    }
    
    cout << endl;
    
    int choice;                                                     // variable for do-while loop
    
    do
    {                                                              // user input menu option
        cout << "The following are your choices.\n";
        cout << "Please enter the number for the selection you want: \n";
        cout << endl;
        cout << "1. Search.\n";
        cout << "2. Print.\n";
        cout << "3. Quit Program\n";
        cout << endl;
        cout << "Enter your selection: ";
        cin >> choice;
        while (choice < 1 || choice > 3)                            // input validation
        {   cout << "The valid choices are 1 through 3.  Please\n"
            << "select one of those." << endl;
            cout << "Enter your selection: ";
            cin >> choice;
        }
        
        switch (choice)
        {
            case 1:                                                 // display function described below
                int searchKey;
                cout << "Please the numerical key value assigned to the name you are looking for: ";
                cin >> searchKey;
                cout << endl;
                if(search(root, searchKey) == true)
                    cout << "Found" << endl;
                else
                    cout << "Not Found" << endl;
                cout << endl;
                break;
            case 2:                                                 // search function described below
                inorder(root);
                cout << endl;
                break;
            case 3:                                                 // ends program
                cout << "Thank you for using this program.\n";
                cout << "Have a nice Day.\n";
                cout << endl;
        }
        
    }while (choice != 3);
    
    return 0;
}