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

struct element{
	int k;
	struct element *parent;
	struct element *lewy;
	struct element *prawy;
};

struct element * bst_wstaw(struct element *root, struct element *nowy);
void inorder(struct element *x);
struct element *bst_min(struct element *x);
struct element *bst_max(struct element *x);
struct element *bst_szukaj(struct element *x, int key);

int main(){
	struct element * root = NULL;
	struct element * nowy = NULL;
	int liczba;
	char z;

	while(1){
		printf("\nCo zrobic: ");
		fflush(stdin);
		z = getchar();

		switch(z){
			case 'd':
				nowy = (struct element*) malloc (sizeof(struct element));
				printf("\nPodaj wartosc: ");
				fflush(stdin);
				scanf("%d",&liczba);
				nowy->k = liczba;
				//!!!!!!!!!!!
				nowy->lewy = NULL;
				nowy->prawy = NULL;
				root = bst_wstaw(root, nowy);
				break;
			
			case 'n':
				nowy = bst_min(root);
				liczba = nowy->k;
				printf("\nMin: %d", liczba);
				break;

			case 'm':
				nowy = bst_max(root);
				liczba = nowy->k;
				printf("\nMax: %d", liczba);
				break;

			case 'w':
				inorder(root);
				break;
			
			case 's':
				printf("\nCo znalezc: ");
				fflush(stdin);
				scanf("%d",&liczba);
				nowy = bst_szukaj(root, liczba);
				if(nowy != NULL)
					printf("\nZnaleziono na adresie: %p",nowy);
				else
					printf("\nNie znaleziono!");
				break;

			case 'q':
				return 0;
		}
	}
}

struct element * bst_wstaw(struct element *root, struct element *nowy){
	struct element *y = NULL;
	struct element *x;

	x = root;

	while(x!=NULL){
		y = x;
		if (nowy->k < x->k)
			x = x->lewy;
		else
			x = x->prawy;
	}
		nowy->parent = y;
		if (y == NULL)
			root = nowy;
		else if(nowy->k < y->k)
			y->lewy = nowy;
		else
			y->prawy = nowy;
	return root;
}

void inorder(struct element *x){
	if (x!=NULL){
		inorder(x->lewy);
		printf("%d\t",x->k);
		inorder(x->prawy);
	}
}

struct element *bst_min(struct element *x){
	while(x->lewy !=NULL)
		x = x->lewy;
	return x;
}

struct element *bst_max(struct element *x){
	while(x->prawy !=NULL)
		x = x->prawy;
	return x;
}

struct element *bst_szukaj(struct element *x, int key){
	while((x != NULL) && (x->k != key)){
		if (key < x->k)
			x = x->lewy;
		else
			x = x->prawy;
	}
	return x;
}