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

typedef struct c
{
    int number;
    struct c *left;
    struct c *right;
}node;

node *newNode(int element)
{
    node *new;
    new = (node *)malloc(sizeof(node));
    if (new == 0)
        return 0;
    new->number = element;
    new->left = 0;
    new->right = 0;

    return new;
}

node *add_element(node *root, int new)
{
    if (root == 0)
        return  newNode(new);

    if (new < root->number)
        root->left = add_element(root->left, new);
    else
        root->right = add_element(root->right, new);

    return root;
}

void print_elementi(node *root)
{
    if (root == 0) return;
    print_elementi(root->left);
    printf("%d -> ", root->number);
    print_elementi(root->right);
}

void customPrint(node *root) // without recursion
{
    if (root != NULL && root->left != NULL)
    {
        printf("%d -> ", root->left->number);
        root = root->left;
        while (root->right != NULL)
        {
            printf("%d ->", root->right->number);
            root = root->right;
        }
    }
}

void print_tree(node *root, int space)
{
    if (root == NULL)
        return;

    space += 5;

    print_tree(root->right, space);

    printf("\n");
    for (int i = 5; i < space; i++) {
        printf(" ");
    }

    printf("%d\n", root->number);

    print_tree(root->left, space);
}

int element_number(node *root)
{
    if (root == 0)
        return 0;

    return 1 + element_number(root->left) + element_number(root->right);
}

int leaf_number(node *root)
{
    if (root == 0)
        return 0;

    if (root->left == 0 && root->right == 0)
        return 1;

    return leaf_number(root->left) + leaf_number(root->right);
}

int element_sum(node *root)
{
    if (root == 0)
        return 0;

    return root->number + element_sum(root->left) + element_sum(root->right);
}

node *min(node *root)
{
    if (root->left == NULL)
        return root;

    return min(root->left);
}

node *delete(node *root, int value)
{
    if (root == NULL)
        return NULL;
    else if (value < root->number)
        root->left = delete(root->left, value);
    else if (value > root->number)
       root->right = delete(root->right, value);
    else
    {

        if (root->left == NULL && root->right == NULL)
        {
            root = NULL;
        }
        else if (root->left == NULL)
        {
            root = root->right;
        }
        else if (root->right == NULL)
        {
            root = root->left;
        }
        else
        {
            node *tempnode = min(root->right);
            root->number = tempnode->number;
            root->right = delete(root->right, tempnode->number);
        }

    }

    return root;
}

int search(node *root, int number)
{

    if (root == 0)
        return 0;

    if (root->number == number)
        return 1;

    if (number < root->number)
        return search(root->left, number);
    else
        return search(root->right, number);

}

int main()
{
    node *root = 0;

    /*Adding elements to the tree*/
    root = add_element(root, 24);
root = add_element(root, 18);
root = add_element(root, 31);
root = add_element(root, 11);
root = add_element(root, 20);
root = add_element(root, 29);
root = add_element(root, 33);
root = add_element(root, 7);
root = add_element(root, 55);
root = add_element(root, 21);


    /*print element*/
    printf("%s", "- ELEMENTS IN THE TREE: ");
    print_element(root);

   print_tree(root, 5);

    printf("%s", "- CUSTOM PRINT: ");
    customPrint(root);

    system("pause");
    return 0;
}