#include "hed.h"

using namespace std;
address allocation(int x) {
    address Root = new Node;
    info(Root) = x;
    left(Root) = NULL;
    right(Root) = NULL;
    return Root;
}

void createTree(BinarySrcTree &T) {
    T.Root = NULL;
}

bool isLeaf(address Root) {
    return (left(Root) == NULL) && (right(Root) == NULL);
}

void insertBST(int x, address &Root) {
    if (Root == NULL) {
            Root = allocation(x);
    }
    else {
            if(x < info(Root)) {
                    insertBST(x,left(Root));
            }else if (x > info(Root)) {
                    insertBST(x, right(Root));
            }
    }
}

void inOrder(address Root) {
    if (Root != NULL) {
            inOrder(left(Root));
            cout<<info(Root)<<", ";
            inOrder(right(Root));
    }
}

address findNode(address Root, int x) {
    if ((Root == NULL) || (info(Root) == x)) {
            return Root;
    }
    else {
            if (x < info(Root)) {
                    findNode(left(Root), x);
            }else if (x > info(Root)) {
                    findNode(right(Root), x);
            }
    }
}

int CountInternalNode(address Root) {
    if (Root == NULL || (isLeaf(Root))) return 0;
    return (1 + CountInternalNode(left(Root)) + CountInternalNode(right(Root)));
}


void printLeaves(address Root) {
    if (Root == NULL) {
            return;
    }
    else {
            if (isLeaf(Root)) {
                    cout<<info(Root)<<", ";
            }
            else if ((left(Root) != NULL) || (right(Root) != NULL)) {
                    printLeaves(left(Root));
                    printLeaves(right(Root));
            }
    }
}

int countLeaves(address Root) {
    if (Root == NULL) return 0;
    int a = countLeaves(left(Root));
    int b = countLeaves(right(Root));
    if (isLeaf(Root)) return 1;
    return a + b;
}