// tree.cpp

#include <iostream>
#include <assert.h>
using namespace std;

class Node; // forward class declaration

class Tree
{
private:
  Node *root;
public:
    Tree();
    ~Tree();
    void insert(int val);
    void preorder();
    void postorder();
    void inorder();
    bool contains(int val);
    int size();
    int height();
    int max();
    int min();
    void remove(int val);
};

class Node
{
private:
    Node *lchild;
    int value;
    Node *rchild;
public:
    Node(int val);
    ~Node();
    void insert(int val);
    void preorder();
    void postorder();
    void inorder();
    bool contains(int val);
    int size();
    int height();
    int max();
    int min();
    void remove(int val);
};

// contructors

Tree::Tree()
{
    root = NULL;
}

Node::Node(int val)
{
    value = val;
    lchild = NULL;
    rchild = NULL;
}

// destructors

Tree::~Tree()
{
    delete root;
    root = NULL;
}

Node::~Node()
{
    if (lchild != NULL)
    {
        delete lchild;
        lchild = NULL;      
    }
    if (rchild != NULL)
    {
        delete rchild;
        rchild = NULL;
    }
}

// insert

void Tree::insert(int val)
{
    if (root != NULL)
    {
        root->insert(val);
    }
    else
    {
        // inserting into an empty tree
        Node *temp = new Node(val);
        root = temp;

        // root = new Node(val);  <<SAME AS ABOVE>>
    }
}

void Node::insert(int val)
{
    Node *p = this;
    Node *q = p;
    while (p != NULL)
    {
        q = p;
        if (val < p->value) 
        {
            p = p->lchild;
        }
        else
        {
            p = p->rchild;
        }
    }
    Node *temp = new Node(val);
    if (val < q->value)
    {
        q->lchild = temp;
    }
    else
    {
        q->rchild = temp;
    }
}

// preorder

void Tree::preorder()
{
    // PFS (Problem for the Student)
}

void Node::preorder()
{
    // PFS (Problem for the Student)
}

// postorder

void Tree::postorder()
{
    // PFS (Problem for the Student)
}

void Node::postorder()
{
    // PFS (Problem for the Student)
}


// inorder

void Tree::inorder()
{
    if (root != NULL)
    {
        root->inorder();
    }
    cout << endl;
}

void Node::inorder()
{
    if (lchild != NULL)
    {
        lchild->inorder();
    }
    cout << value << " ";
    if (rchild != NULL)
    {
        rchild->inorder();
    }
}

// contains

bool Tree::contains(int val)
{
    // short-circuit evaluation
    return root != NULL && root->contains(val);
}

bool Node::contains(int val)
{
    if (value == val)
    {
        return true;
    }
    else if (value < val)
    {
        return rchild != NULL && rchild->contains(val);
    }
    else
    {
        return lchild != NULL && lchild->contains(val);
    }
}

// size

int Tree::size()
{
    if (root != NULL)
    {
        return root->size();
    }
    else
    {
        return 0;
    }
}

int Node::size()
{
    int lsize = (lchild != NULL)? lchild->size(): 0;
    int rsize = (rchild != NULL)? rchild->size(): 0;
    return lsize + rsize + 1;
}

int Tree::height()
{
    if (root != NULL)
    {
        return root->height();
    }
    else
    {
        return 0;
    }
}

int Node::height()
{
    int lheight = (lchild != NULL)? lchild->height(): 0;
    int rheight = (rchild != NULL)? rchild->height(): 0;
    return 1 + ((lheight > rheight)? lheight: rheight);
}

// max

int Tree::max()
{
    assert(root != NULL); // i.e. Empty trees do not have a max
    return root->max();
}

int Node::max()
{
    Node *p = this;
    int maximum;
    while (p != NULL)
    {
        maximum = p->value;
        p = p->rchild;
    }
    return maximum;
}

int Tree::min()
{
    assert(root != NULL); // i.e. Empty trees do not have a min
    return root->min();
}

int Node::min()
{
    Node *p = this;
    int minimum;
    while (p != NULL)
    {
        minimum = p->value;
        p = p->lchild;
    }
    return minimum;
}

// remove

void Tree::remove(int val)
{
    if (root != NULL && contains(val))
    {
        root->remove(val);
    }
}

void Node::remove(int val)
{
    Node *p = this;
    while (p->value != val)
    {
        if (p->value < val)
        {
            p = p->rchild;
        }
        else
        {
            p = p->lchild;
        }
    }
    // p now points to node that will be removed

}



int main(int argc, char const *argv[])
{
    Tree *t = new Tree();
    t->insert(50);
    t->insert(20);
    t->insert(80);
    t->insert(85);
    t->insert(95);
    t->insert(90);
    t->insert(10);
    t->insert(15);
    t->insert(5);
    t->insert(30);
    t->insert(40);
    t->insert(18);
    t->insert(75);
    t->inorder();
    cout << "There are " << t->size() << " nodes in the tree." << endl;
    cout << "Height == " << t->height() << endl;
    if (t->contains(30))
    {
        cout << "30 in tree." << endl;
    }
    else
    {
        cout << "No 30." << endl;
    }
    if (t->contains(70))
    {
        cout << "70 in tree." << endl;
    }
    else
    {
        cout << "No 70." << endl;
    }
    cout << "Max is " << t->max() << endl;
    cout << "Min is " << t->min() << endl;
    return 0;
}