#include "binary_tree.h"
#include "iostream"
using namespace std;

int max(int a, int b)
{ if(a>b) return a;
    else return b;
}

tree_node::tree_node(int x, tree_node *l, tree_node *r) {
    val = x;
    left_child = l;
    right_child = r;
}

binary_tree::binary_tree()
{ root = 0;}

binary_tree::binary_tree(int x)
{ root = new tree_node(x, 0, 0); }

void destruct(tree_node* r)
{   if(r)
    {   destruct(r->left_child);
        destruct(r->right_child);
        delete r;}
}

binary_tree::~binary_tree() {
    destruct(root);
}

void preorder(tree_node* r){
    if(r){
        cout<<r->val<<' ';
        preorder(r->left_child);
        preorder(r->right_child);
    }
}

void binary_tree::print_pre_order()
{preorder(root);
    cout<<endl;}

void inorder(tree_node* r){
    if(r) {
        inorder(r->left_child);
        cout << r->val << ' ';
        inorder(r->right_child);
    }

}

void binary_tree::print_in_order()
{inorder(root);
    cout<<endl;}


void postorder(tree_node* r){
    if(r){
        postorder(r->left_child);
        postorder(r->right_child);
        cout<<r->val<<' ';}
}

void binary_tree::print_post_order()
{postorder(root);
    cout<<endl;}

bool binary_tree::add(int x)
{  tree_node* temp = root, *temp_prev=temp;
    while(temp && temp->val != x) {
        temp_prev = temp;
        if (x > temp->val)
            temp = temp->right_child;
        else
            temp = temp->left_child;
    }
    if(temp)
        return false;
    else{
        if(temp_prev){
            tree_node* new_child = new tree_node(x,0,0);
            if(temp_prev->val>x)
                temp_prev->left_child = new_child;
            else temp_prev->right_child = new_child;
        }
        else root = new tree_node(x, 0, 0);
        return true;
    }
}

bool binary_tree::find(int x) {
    tree_node* temp = root;
    while(temp)
        if(x>temp->val)
            temp=temp->right_child;
        else if(x<temp->val)
            temp=temp->left_child;
        else return true;

    return false;
}


int max_height(tree_node* r)
{ if(r)
        return 1+max(max_height(r->left_child), max_height(r->right_child));
    else return 0;}

int binary_tree::height() {
    return max_height(root); }

int count_size(tree_node* r)
{
    if(r)
        return 1 + count_size(r->left_child) + count_size(r->right_child);
    else return 0;
}


int binary_tree::size() {
    return count_size(root); }

int print1(tree_node* r, int k){
    if(r) {
        print1(r->right_child,k+1);
        for (int i = 0; i < k*3; i++)
            cout << ' ';
        cout<<r->val<< endl;
        print1(r->left_child, k+1);
        return 0;
    }
    else {
        for(int i = 0; i < k*3; i++)
            cout<<' ';
        cout<< '@'<< endl;
        return 0;
    }
}

void binary_tree::print() {
    print1(root, 0);
}