/*
Drzewo bst posortowane
Dodawanie OK
Wypisywanie OK
Sprawdzanie czy drzewo bst
*/
#include <stdio.h>
#include <stdlib.h>

//typedef struct listek;

struct listek {
	int wartosc;
	struct listek* lewy;
	struct listek* prawy;
	//struct listek* tata;
};
struct drzewo {
	struct listek* szczyt_drzewa;
};
struct listek* konstruktor_listka(int wartosc) {
	struct listek* nowy_lisc;
	nowy_lisc = (struct listek*)malloc(sizeof(struct listek));
	nowy_lisc->wartosc = wartosc;
	nowy_lisc->lewy = NULL;
	nowy_lisc->prawy = NULL;
	//nowy_lisc->tata = NULL;
	return nowy_lisc;
}


void dodaj_listek(struct drzewo* drzewo, int wartosc) {
	if (drzewo->szczyt_drzewa == NULL) drzewo->szczyt_drzewa = konstruktor_listka(wartosc);
	else {
		int znalazlem_miejsce = 0;
		struct listek* nowy_lisc;
		nowy_lisc = drzewo->szczyt_drzewa;
		while (znalazlem_miejsce == 0) {
			if (wartosc <= nowy_lisc->wartosc) {
				if (nowy_lisc->lewy == NULL) {
					nowy_lisc->lewy = konstruktor_listka(wartosc);
					//nowy_lisc->lewy->tata = nowy_lisc;
					znalazlem_miejsce = 1;
				}
				else nowy_lisc = nowy_lisc->lewy;
			}
			else {
				if (nowy_lisc->prawy == NULL) {
					nowy_lisc->prawy = konstruktor_listka(wartosc);
					//nowy_lisc->prawy->tata = nowy_lisc;
					znalazlem_miejsce = 1;
				}
				else nowy_lisc = nowy_lisc->prawy;
			}
		}
	}
}

void wypisz_listek(struct listek* lisc) {
	if (lisc != NULL) {
		wypisz_listek(lisc->lewy);
		printf("%d ", lisc->wartosc);
		wypisz_listek(lisc->prawy);
	}
}
void wypisz_drzewko(struct drzewo* drzewo) {
	wypisz_listek(drzewo->szczyt_drzewa);
}

/*
if the node is the left child of its parent,
then it must be smaller than(or equal to)
the parent and it must pass down the value
from its parent to its right subtree to make
sure none of the nodes in that subtree is
greater than the parent

if the node is the right child of its parent,
then it must be larger than the parent
and it must pass down the value from its parent
to its left subtree to make sure
none of the nodes in that subtree
is lesser than the parent.
*/

int czy_bst(struct listek* lisc, int wartosc_min, int wartosc_max) {
	if (lisc == NULL) return 1;
	if (lisc->wartosc < wartosc_min || lisc->wartosc > wartosc_max) return 0;
	if (czy_bst(lisc->lewy, wartosc_min, lisc->wartosc) == 1 &&
		czy_bst(lisc->prawy, lisc->wartosc, wartosc_max) == 1)return 1;
	else return 0;
}
void powiedz_czy_drzewko_jest_bst(struct drzewo* drzewko) {
	if (czy_bst(drzewko->szczyt_drzewa, 0, 1000000)) printf("\ntak, drzewko jest drzewkiem bst");
	else printf("\ndrzeko nie jest bst");
}

int main() {
	struct drzewo klon;
	klon.szczyt_drzewa = NULL;
	dodaj_listek(&klon, 10);
	dodaj_listek(&klon, 5);
	dodaj_listek(&klon, 7);
	dodaj_listek(&klon, 6);
	dodaj_listek(&klon, 2);
	dodaj_listek(&klon, 3);
	dodaj_listek(&klon, 25);
	dodaj_listek(&klon, 5);
	dodaj_listek(&klon, 5);
	dodaj_listek(&klon, 5);
	dodaj_listek(&klon, 33);
	dodaj_listek(&klon, 23);
	dodaj_listek(&klon, 6);
	dodaj_listek(&klon, 1);
	wypisz_drzewko(&klon);
	powiedz_czy_drzewko_jest_bst(&klon);
	return 0;
}