#include<stdio.h>
#include<stdlib.h>
struct element{
    struct element *p;
    int key;
    struct element *left;
    struct element *right;
};
struct element* bst_wstaw(struct element* T,struct element* Z);
struct element* bst_szukaj(struct element* x,int k);
struct element* bst_max(struct element* x);
struct element* bst_min(struct element* x);
void bst_wyswietl(struct element* x);

main()
{
    struct element* root=NULL, *nowy=NULL,*max,*min;
    char z;
    int liczba;
    while(1)
    {
        printf("\nWybierz co chcesz zrobic");
        printf("\nd - dodac");
        printf("\ns - szukac");
        printf("\nu - usunac");
        printf("\nw - wyswietlic");
        printf("\nq - wyjscie\n");
        fflush(stdin);
        z=getchar();
        switch(z)
        {
            case 'd':
                nowy=(struct element*)malloc(sizeof(struct element));
                printf("\nPodaj wartosc elementu do wstawienia:> ");
                scanf("%d",&liczba);
                nowy->key=liczba;
                nowy->left=NULL;
                nowy->right=NULL;
                root=bst_wstaw(root,nowy);
                break;
            case's':
                printf("\nPodaj wartosc elementu do wyszukania:> ");
                scanf("%d",&liczba);
                nowy=bst_szukaj(root,liczba);
                if(nowy!=NULL)
                    printf("\nZnaleziono element!");
                else
                    printf("\nBrak szukanego elementu!");
                break;
            case 'm':max=bst_max(root)
                         printf("Wartosc maksymalna: %d",max->key);
                break;

            case 'w':
                printf("\n");
                bst_wyswietl(root);
                break;
            case 'q':return 0;
        }
    }
}
struct element* bst_wstaw(struct element* T,struct element* Z)
{
    struct element* x=T, *y=NULL;
    while(x!=NULL)
    {
        y=x;
        if(Z->key < x->key) x=x->left;
        else x=x->right;
    }
        Z->p=y;
        if(y==NULL) T=Z;
        else if(Z->key < y->key) y->left=Z;
        else y->right=Z;

    return T;
}
struct element* bst_szukaj(struct element* x,int k)
{
    if(x==NULL||k==x->key)
        return x;
    if(k < x->key)
        return bst_szukaj(x->left,k);
    return bst_szukaj(x->right,k);
}
struct element* bst_max(struct element* x)
{
    while(x->right!=NULL)
        x=x->right;
    return x;
}
void bst_wyswietl(struct element* x)
{
    if(x!=NULL)
    {
        bst_wyswietl(x->left);
        printf("%d ",x->key);
        bst_wyswietl(x->right);
    }
}
struct element* bst_min(struct element* x)
{
    while(x->left!=NULL)
        x=x->left;
    return x;
}