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

struct ed
{
    int wartosc;
    struct ed *prawy;
    struct ed *lewy;
    struct ed *rodzic;
};

typedef struct ed ed;

ed *min(ed *korzen)
{
    if (korzen -> lewy == NULL)
        return korzen;
    else
        korzen = min(korzen->lewy);
}

ed *max(ed *korzen)
{
    if (korzen -> prawy == NULL)
        return korzen;
    else
        korzen = max(korzen->prawy);
}

ed *dodaj(ed *korzen, int x)
{
    /* If the tree is empty return an empty node */
    if (korzen == NULL)
    {
        ed *q = (ed*)malloc(sizeof(ed));
        q -> wartosc = x;
        q -> lewy = NULL;
        q -> prawy = NULL;
        return q;
    }

    /* Otherwise, recur down the tree */
    if (x < korzen->wartosc)
    {
        korzen->lewy = dodaj(korzen->lewy, x);
        korzen->lewy->rodzic = korzen;
    }

    else if(x > korzen->wartosc)
    {
        korzen->prawy = dodaj(korzen->prawy, x);
        korzen->prawy->rodzic = korzen;
    }

    /* return the (unchanged) node pointer */
    return korzen;
}

ed *usun(ed* korzen, int x)
{
    if(korzen == NULL) return korzen;
    if(x < korzen->wartosc)
        korzen->lewy = usun(korzen->lewy, x);
    else if(x > korzen->wartosc)
        korzen->prawy = usun(korzen->prawy, x);
    else
    {
        if(korzen->lewy == NULL)
        {
            ed *tymczasowy = korzen->prawy;
            free(korzen);
            return tymczasowy;
        }
        else if(korzen->prawy == NULL)
        {
            ed *tymczasowy = korzen->lewy;
            free(korzen);
            return tymczasowy;
        }
         ed *tymczasowy = min(korzen->prawy);
         korzen->wartosc = tymczasowy->wartosc;
         korzen->prawy = usun(korzen->prawy, tymczasowy->wartosc);
    }
    return korzen;
}

ed *szukaj(ed *korzen, int x)
{
    if(korzen == NULL || korzen->wartosc == x)
        return korzen;
    if(korzen->wartosc < x)
        return szukaj(korzen->prawy, x);
    return szukaj(korzen->lewy, x);
}

void drukuj(ed *korzen, int spacje)
{
    if(korzen == NULL)
        return;
    int i;
    spacje += 10;
    drukuj(korzen->prawy, spacje);
    printf("\n");
    for(i=10; i<spacje; i++)
        printf(" ");
    printf("%d\n", korzen->wartosc);
    drukuj(korzen->lewy, spacje);
}

ed *poprzednik(ed *korzen)
{
    if(korzen->lewy)
        return max(korzen->lewy);
    else
    {
        while(korzen->rodzic && (korzen->rodzic->lewy == korzen))
            korzen = korzen->rodzic;
    }
    return korzen->rodzic;
}

ed *nastepnik(ed *korzen)
{
    if(korzen->prawy)
        return max(korzen->prawy);
    else
    {
        while(korzen->rodzic && (korzen->rodzic->prawy == korzen))
            korzen = korzen->rodzic;
    }
    return korzen->rodzic;
}

int ile_x(ed *korzen, int x) // zlicza liczbe x-ów w drzewie
{
    if(korzen == 0)
        return 0;
    int pom = 0;
    if(korzen->wartosc == x)
        pom = 1;
    return ile_x(korzen->lewy, x) + ile_x(korzen->prawy, x) + pom;
}

bool czy_te_same(ed *korzen_1, ed *korzen_2)
{
    if(korzen_1 == 0) // a¿ skoñczymy sprawdzaæ wartoœci 1 drzewa w 2 drzewie
        return true;
    if(ile_x(korzen_2, korzen_1->wartosc) > 0) // przeszukuje w drzewie nr 2 wartosci z 1 drzewa
        return czy_te_same(korzen_1->lewy, korzen_2) && czy_te_same(korzen_1->prawy, korzen_2);
    else
        return false;
}

int liczba_lisci(ed *korzen)
{
    if(korzen == NULL)
        return 0;
    if(korzen->lewy == NULL && korzen->prawy == NULL)
        return 1;
    else
        return liczba_lisci(korzen->lewy) + liczba_lisci(korzen->prawy);
}

void sumaLisci(ed *korzen, int *suma)
{
    if(korzen != NULL)
        return;
    if(korzen->lewy != NULL && korzen->prawy != NULL)
        *suma += korzen->wartosc;
    sumaLisci(korzen->lewy, suma);
    sumaLisci(korzen->prawy, suma);
}

int liczebnosc(ed *korzen)
{
    if(korzen == NULL)
        return 0;
    else
        return(liczebnosc(korzen->lewy) + liczebnosc(korzen->prawy) + 1);
}

int liczebnosc(wsk T)
{
    if(T == NULL)
        return 0;
    else
        return(liczebnosc(T->lewy) + liczebnosc(T->prawy) + 1);
}

int wywazenie(wsk T)
{
    if(T == NULL)
        return 0;
    else
        return max(abs(liczebnosc(korzen->lewy) - liczebnosc(korzen->prawy)), wywazenie(korzen->lewy), wywazenie(korzen->prawy));
}

int glebokosc(ed *korzen)
{
    if(korzen == NULL)
        return 0;
    else
    {
        int glebokoscL = glebokosc(korzen->lewy);
        int glebokoscR = glebokosc(korzen->prawy);
        if(glebokoscL > glebokoscR)
            return(glebokoscL + 1);
        else return(glebokoscR + 1);
    }
}

void lustrzane_odbicie(ed *korzen)
{
    if(korzen == NULL)
        return;
    else
    {
        ed *tymczasowy;
        lustrzane_odbicie(korzen->lewy);
        lustrzane_odbicie(korzen->prawy);
        tymczasowy = korzen->lewy;
        korzen->lewy = korzen->prawy;
        korzen->prawy = tymczasowy;
    }
}