Binary Search Tree

/*
Laboratory activity:
1. Write a c++ program that sort the following numbers and build binary search tree with the root of 10.
    Given:
        {80, 20, 100, 10, 40, 90, 30, 50, 35}

2. From problem 1, insert {65, 75, 15} into the tree.

3. Draw the Binary Search Tree considering the data given from problem 1 and 2.

4. from prob. 1 and 2, display the BST after deleting the level 2 parent node(s).
*/

#include <iostream>
#include <queue>
#include <iomanip>

using namespace std;

class node {
    public:
        int value;
        node* left;
        node* right;

        node (int nodevalue){
            value = nodevalue;
            left = NULL;
            right = NULL;
        }
};

node* add(node*, int);
void levelorder(node*);
void bubblesorttrial(int arr[], int);
void output(int arr[], const int);
void searchlevel(node*);
node* deletenode(node*, int);

int main (){
    const int size = 9;
    const int sizea = 3;
    int valuearray[size] = {80, 20, 100, 10, 40, 90, 30, 50, 35};    //the given values
    int addarray[sizea] = {65, 75, 15};    //given values to be inserted from problem 2

    cout << "\n The given values are: ";
    output(valuearray, size);
    cout << "\n The given values to be added are: ";
     output(addarray, sizea);
    bubblesorttrial(valuearray, size);    //bubblesorted array, a copypasta from the past lab activities
    cout << "\n The given values after sort are: ";
    output(valuearray, size);

    node* root = new node(valuearray[0]);

    for (int h = 1; h < size; h++){
        int value = valuearray[h];
        add(root, value);
    }

    cout << "\n The BST of the sorted values with the root of 10 are: ";
    levelorder(root);

    for (int h = 0; h < sizea; h++){
        int valuea = addarray[h];
        add(root, valuea);
    }

    cout << "\n The BST after adding the values are: ";
    levelorder(root);
    cout << "\n The BST after deleting the level 2 values are: ";
    searchlevel(root);
    levelorder(root);

    return 0;
}

node* add(node* root, int value){
    if (root == NULL) {
        root = new node(value);
    }
    else if (value <= root->value){
        root->left = add(root->left, value);
    }
    else if (value > root->value){
        root->right = add(root->right, value);
    }

    return root;
}

void levelorder(node* root){
    queue<node*> q;

    q.push(root);

    while (!q.empty()){
        node* nodea = q.front();

        cout << nodea->value << setw(4);

        q.pop();

        if (nodea->left != NULL){
            q.push(nodea->left);
        }
        if (nodea->right != NULL){    //for some reason, compiler skips this if its on "else if" condition
            q.push(nodea->right);
        }
    }
}

void bubblesorttrial(int arr[], int size){
    int hold;
    for (int pass = 1; pass < size - 1; pass ++){
        for (int i = 0; i < size - 1; i ++){
            if (arr[i] > arr[i + 1]){
                hold = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = hold;
            }
        }
    }
}

void output(int valuearray[], const int size){
    for (int h = 0; h < size; h++){
        cout << valuearray[h] << setw(4);
    }
}

void searchlevel(node* root){
    queue<node*> q;
    int h = 0;    //creates a tally rating

    q.push(root);

    while (!q.empty()){
        node* nodea = q.front();

            if (h == 2){    //if 2(which is the level 2) then delete nodes
                deletenode(root, nodea->value);
            }

        q.pop();

        if (nodea->left != NULL){
            q.push(nodea->left);
        }
        if (nodea->right != NULL){
            q.push(nodea->right);
            h++;
        }
    }
}

node* deletenode(node* nodea, int valuea){
    if (nodea == NULL){
        return nodea;
    }

    else if (valuea < nodea->value){
        nodea->left = deletenode(nodea->left, valuea);
    }
    else if (valuea > nodea->value){
        nodea->right = deletenode(nodea->right, valuea);
    }

    else {
        if (nodea->left == NULL && nodea->right == NULL){
            delete nodea;
            nodea = NULL;
            return nodea;
        }
        else if (nodea->left == NULL){
            node* hold = nodea;
            nodea = nodea->right;
            delete hold;
            return nodea;
        }
        else if (nodea->right == NULL) {
            node* hold = nodea;
            nodea = nodea->left;
            delete hold;
            return nodea;
        }
    }
    return nodea;
}

/*
the bst illustration before sort:
           10                      --level 0
             \
             80                    --level 1
           /    \
         20      100               --level 2
       /   \      /
     15    40    90                --level 3
          /  \
        30    50                   --level 4
         \       \
         35       65               --level 5
                    \
                     75            --level 6

 the bst illustration after sort:
 10                                    --level 0
   \
    20                                 --level 1
   /   \
 15     30                             --level 2
           \
            35                         --level 3
               \
                40                     --level 4
                   \
                    50                 --level 5
                       \
                        80             --level 6
                      /    \
                    65      90         --level 7
                     \         \
                     75         100    --level 8

the bst illustration after delete past level 2:
 10                                --level 0
    \
     20                            --level 1
        \
         35                        --level 2
            \
             40                    --level 3
                \
                 50                --level 4
                    \
                     80            --level 5
                   /    \
                 65      90        --level 6
                  \        \
                  75        100    --level 7
*/