#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
#include <math.h>
#include <locale.h>
#define SIZE 10

struct node
{
    int data;
    struct node *right_child;
    struct node *left_child;
};




struct node* find_minimum(struct node *root)
{
    if(root == NULL)
        return NULL;
    else if(root->left_child != NULL)
        return find_minimum(root->left_child);
    return root;
}


struct node* new_node(int x)
{
    struct node *p;
    p = malloc(sizeof(struct node));
    p->data = x;
    p->left_child = NULL;
    p->right_child = NULL;

    return p;
}

struct node* insert(struct node *root, int x)
{

    if(root==NULL)
        return new_node(x);
    else if(x>root->data)
        root->right_child = insert(root->right_child, x);
    else
        root->left_child = insert(root->left_child,x);
    return root;
}


struct node* delete(struct node *root, int x)
{

    if(root==NULL)
        return NULL;
    if (x>root->data)
        root->right_child = delete(root->right_child, x);
    else if(x<root->data)
        root->left_child = delete(root->left_child, x);
    else
    {
        if(root->left_child==NULL && root->right_child==NULL)
        {
            free(root);
            return NULL;
        }

        else if(root->left_child==NULL || root->right_child==NULL)
        {
            struct node *temp;
            if(root->left_child==NULL)
                temp = root->right_child;
            else
                temp = root->left_child;
            free(root);
            return temp;
        }

        else
        {
            struct node *temp = find_minimum(root->right_child);
            root->data = temp->data;
            root->right_child = delete(root->right_child, temp->data);
        }
    }
    return root;
}

void display(struct node *root)
{
    int sum = 0;

    if(root == NULL)
        return;
    else
    {

        display(root->left_child);


        printf("%d ", root->data);
        sum+= root->data;



        display(root->right_child);



    }
    printf("sum: %d\n",sum);


}
int count_height(struct node *root)
{
    if(root!=NULL)
    {
        int a = count_height(root->left_child);
        int b = count_height(root->right_child);
        if (a>b)

            return a+1;
        else
            return b+1;
    }
    else
        return 0;

}

void count_sum(struct node *root, int sum, int level, int num_levels)
{
    sum = 0;
    if(root == NULL)
       return;

    else {
        sum += root->data;



        count_sum(root->left_child, sum, level+1, num_levels);
        count_sum(root->right_child, sum, level+1, num_levels);




    }
    printf("lvl%d, sum: %d\n", level, sum);
    return;

}



int main()
{

    struct node *root;
    int y, level=0, sum = 0, num_levels;

    printf("Введите вершину дерева\n");
    scanf("%d", &y);
    root = new_node(y);

    int choice = 10;




    while(choice!=5)
    {
        printf("\n1.Добавить элемент\n2.Удалить элемент\n3.Показать элементы очереди\n4.Показать сумму элементов на уровнях\n5.Выход\n");
        scanf("%d", &choice);
        switch (choice)
        {
        case 1:
            printf("Введите элемент\n");

            scanf("%d", &y);
            insert(root,y);
            break;

        case 2:
            printf("Введите элемент\n");

            scanf("%d", &y);
            delete(root, y);
            break;

        case 3:
            printf("элементы: ");

            display(root);
            break;
        case 4:
            num_levels = count_height(root);
            count_sum(root, sum, level, num_levels);



            break;

        case 5:
            exit(-1);
        default:
            printf("\nПовторите ввод\n");
        }

    }



    return 0;
}