#include <stdio.h>
#include <stdlib.h>

#define NODE_VALUES_1_SIZE 7
#define NODE_VALUES_2_SIZE 5

/* Nome: Reberth
 *
 * Turma: Regina - RA: 141589
 *
 * */

typedef struct BinaryNode {
    int value;
    struct BinaryNode *left;
    struct BinaryNode *right;
} BNode;

BNode *createBinaryNode(int value, BNode *left, BNode *right) {
    BNode *newNode = (BNode *) malloc(sizeof(BNode));
    newNode->value = value;
    newNode->left = left;
    newNode->right = right;
    return newNode;
}

BNode *createABBNode(BNode *root, int value) {
    /*
     * root =>
     *    - Is NULL
     *       Create binary node with no childs
     *    - Is not NULL
     *      Check if the new child was be placed on the left/right
     * */
    if (root == NULL) {
        return createBinaryNode(
                value,
                NULL,
                NULL
        );
    } else if (root->value > value) {
        return createBinaryNode(
                root->value,
                createABBNode(
                        root->left,
                        value
                ),
                root->right
        );
    } else if (root->value < value) {
        return createBinaryNode(
                root->value,
                root->left,
                createABBNode(
                        root->right,
                        value
                )
        );
    }
    return root;
}


void infixBinaryRoot(BNode *root) {
    /*
     * Print on infix order
     * */
    if (root != NULL) {
        infixBinaryRoot(root->left);
        printf("%i ", root->value);
        infixBinaryRoot(root->right);
    }
}

BNode *clearBinaryRoot(BNode *root) {
    /*
     * Clear node, last to first.
     * */
    if (root != NULL) {
        clearBinaryRoot(root->left);
        clearBinaryRoot(root->right);
        free(root);
    }
    return NULL;
}

BNode *createBinaryRoot(BNode *root, int *nodeValues, int size) {
    for (int i = 0; i < size; i++) {
        root = createABBNode(root, nodeValues[i]);
    }
    return root;
}

/* função verif_se_ABB */
int checkIfIsABBBinary(BNode *root) {
    if (root != NULL) {
        /* Existe Lado esquerdo, não existe lado direito */
        /* Não existe lado esquerdo, existe lado direito */
        /* Não existe lado esquerdo, não existe lado direito */
        /* Existe lado esquerdo, existe lado direito */

        if (root->left != NULL && root->right != NULL) {
            if (root->left->value > root->value || root->right->value < root->value) {
                return 0;
            } else {
                return 1;
            }
        } else if (root->left != NULL && root->right == NULL) {
            if (root->left->value > root->value) {
                return 0;
            } else {
                return 1;
            }
        } else if (root->left == NULL && root->right != NULL) {
            if (root->right->value < root->value) {
                return 0;
            } else {
                return 1;
            }
        } else {
            return 1;
        }
    } else {
        return 0;
    }
}

/*função une_ABB*/
BNode *combineABBs(BNode *root, BNode *bRoot1, BNode *bRoot2) {
    /* bRoot1 and bRoot2 =>
     *    - Both are different than NULL;
     *        -> Create ABB Node then call combineABBs again (for left and right of bRoot1/bRoot2)
     *    - bRoot2 is NULL;
     *        -> Create ABB Node then call combineABBs again (for left and right of bRoot2)
     *    - bRoot1 is NULL;
     *        -> Create ABB node then call combine ABBs again (for left and right of bRoot1);
     *    - Both are NULL
     *        -> Return root
     * */
   if (bRoot1 != NULL && bRoot2 != NULL) {
       if (bRoot1->value > bRoot2->value) {
           root = createABBNode(root, bRoot1->value);
           root = combineABBs(root, bRoot1->left, bRoot2);
           root = combineABBs(root, bRoot1->right, bRoot2);
       } else if (bRoot1->value < bRoot2->value) {
           root = createABBNode(root, bRoot2->value);
           root = combineABBs(root, bRoot1, bRoot2->left);
           root = combineABBs(root, bRoot1, bRoot2->right);
       } else {
           root = createABBNode(root, bRoot1->value);
           root = combineABBs(root, bRoot1->left, bRoot2->left);
           root = combineABBs(root, bRoot1->right, bRoot2->right);
       }
   } else if (bRoot1 != NULL && bRoot2 == NULL) {
       root = createABBNode(root, bRoot1->value);
       root = combineABBs(root, bRoot1->left, NULL);
       root = combineABBs(root, bRoot1->right, NULL);
   } else if (bRoot1 == NULL && bRoot2 != NULL) {
      root = createABBNode(root, bRoot2->value);
      root = combineABBs(root, NULL, bRoot2->left);
      root = combineABBs(root, NULL, bRoot2->right);
   }
   return root;
}

int main() {
    int nodeValues1[] = {10, 8, 5, 9, 4, 15, 20};
    int nodeValues2[] = {8, 4, 20, 15, 25};
    BNode *binaryRoot1 = NULL;
    BNode *binaryRoot2 = NULL;

    BNode *combinedBinaryRoot = NULL;

    printf("Initializing program...\n");

    binaryRoot1 = createBinaryRoot(binaryRoot1, nodeValues1, NODE_VALUES_1_SIZE);
    binaryRoot2 = createBinaryRoot(binaryRoot2, nodeValues2, NODE_VALUES_2_SIZE);

    if (binaryRoot1 == NULL || binaryRoot2 == NULL) {
        printf("Error on initializing program. Please try again...\n");
        return 0;
    } else {
        printf("Programa iniciado com sucesso!\n");
    }

    printf("Infix binary root 1 =>");
    infixBinaryRoot(binaryRoot1);

    printf("\nInfix binary root 2 =>");
    infixBinaryRoot(binaryRoot2);

    printf("\nBinary root 1 is ABB? => %i\n", checkIfIsABBBinary(binaryRoot1));

    combinedBinaryRoot = combineABBs(combinedBinaryRoot, binaryRoot1, binaryRoot2);
    if (combinedBinaryRoot == NULL) {
        printf("Error on combine binarys ABB. Please try again.\n");
    } else {
        printf("Combined infix combined binary root => ");
        infixBinaryRoot(combinedBinaryRoot);
    }

    printf("\nStarting clean of program...\n");
    binaryRoot1 = clearBinaryRoot(binaryRoot1);
    binaryRoot2 = clearBinaryRoot(binaryRoot2);
    printf("Successful clean program...\n");
    printf("Exiting...\n");
    printf("Bye!\n");
    return 0;
}