/*
*       for n random numbers:
*               if root is NULL
*                       make number be the root
*               else if number is LESS THAN the root
*                       add number to the LEFT subtree
*               else if number is GREATER THAN the root
*                       add number to the RIGHT subtree
*               else
*                       (do something about it being equal)
*/
#include <stdio.h>
#include <stdlib.h>     // atoi(), random(), srand();  malloc()
// NOTE: the lab computers throw a warning about random(), but the program works.
#include <time.h>       // time()

struct Node {
    int value;
    struct Node *left, *right;
} ;

struct Node *newnode(int value);
void add_to(struct Node *rootp, int value);
void display_tree(struct Node *rootp);

int main(int argc, char **argv)
{
    unsigned n_numbers = 10;
    if (argc >= 2)
        n_numbers = atoi(argv[1]);

    srand( time(NULL) );

    struct Node *rootp = NULL;

    for (int i = 0; i < n_numbers; i++) {
        int value = random() % 100;

        if (rootp == NULL) {
            rootp = newnode(value);
//  DON'T BOTHER DOING THIS, JUST USE add_to() !!!  SEE BELOW.
//
//      } else if (value < rootp->value) {
//          if (rootp->left == NULL)
//              rootp->left = newnode(value);
//          else
//              add_to(rootp->left, value);
//      } else if (value > rootp->value) {
//          if (rootp->right == NULL)
//              rootp->right = newnode(value);
//          else
//              add_to(rootp->right, value);
//      } else {
//          printf("%d is equal\n", value);     // something to do
//      }
        } else
            add_to(rootp, value);
    }

    display_tree(rootp);

    return 0;
}

struct Node *newnode(int value)
{
    struct Node *p = malloc( sizeof(struct Node) );
    p->value = value;
    p->left = p->right = NULL;
    return p;
}

// Add a value into the given (sub)tree:
void add_to(struct Node *rootp, int value)
{
    if (value < rootp->value) {         // go left?
        if (rootp->left == NULL)
            rootp->left = newnode(value);
        else
            add_to(rootp->left, value);

    } else if (value > rootp->value) {  // go right?
        if (rootp->right == NULL)
            rootp->right = newnode(value);
        else
            add_to(rootp->right, value);

    } else {
        printf("%d is equal\n", value); // something to do
    }
}

void display_tree(struct Node *rootp)
{
    if (rootp == NULL)
        return;
    else {
        display_tree(rootp->left);
        printf("%5d\n", rootp->value);
        display_tree(rootp->right);
    }
}