% drzewo(D) -- gdy D jest drzewem

drzewo(leaf).

drzewo(node(TL, _D, TR)) :-
	drzewo(TL),
	drzewo(TR).

% allSmaller(T, E) gdy wszystkie elementy drzewa T są mniejsze niż E

allSmaller(leaf, _E).

allSmaller(node(TL, D, TR), E) :-
	D < E,
	allSmaller(TL, E),
	allSmaller(TR, E).

% allGreater(T, E) gdy wszystkie elementy drzewa T są większe niż E

allGreater(leaf, _E).

allGreater(node(TL, D, TR), E) :-
	D > E,
	allGreater(TL, E),
	allGreater(TR, E).

% getMin(T, E) gdy E jest elementem minimalnym drzewa BST T

getMin(node(leaf, D, _), D).

getMin(node(node(TL, DL, TR), _, _), M) :-
	getMin(node(TL, DL, TR), M).

% getMax(T, E) gdy E jest elementem minimalnym drzewa BST T

getMax(node(_, D, leaf), D).

getMax(node(_, _, node(TL, DL, TR)), M) :-
	getMax(node(TL, DL, TR), M).

% drzewoBST(T) gdy T jest posortowanym drzewem BST (Binary Search Tree)

drzewoBST(leaf).

drzewoBST(node(TL, D, TR)) :-
	getMin(node(TL, D, TR), Min),
	getMax(node(TL, D, TR), Max),
	drzewoBST(Min, node(TL, D, TR), Max).

% drzewoBST(Min, T, Max) gdy T jest drzewem BST o wartościach pomiędzy Min a Max (nieostro)

drzewoBST(_Min, leaf, _Max).

drzewoBST(Min, node(TL, D, TR), Max) :-
	Min =< D,
	D =< Max,
	drzewoBST(Min, TL, D),
	drzewoBST(D,   TR, Max).

% insertBST(Tree, Elem, R) gdy po wstawieniu do drzewa BST Tree elementu Elem powstaje R
% tutaj traktujemy drzewo jako multizbior - te same wartosci moga wystepowac wiele razy

insertBST(leaf, E, node(leaf, E, leaf)).

insertBST(node(TL, D, TR), E, node(RL, D, TR)) :-
	E =< D,
	insertBST(TL, E, RL).

insertBST(node(TL, D, TR), E, node(TL, D, RR)) :-
	E > D,
	insertBST(TR, E, RR).


% wypiszBSTbad(T, L) gdy L to lista zlozona z elementow drzewa BST --- bez akumulatora

wypiszBSTbad(leaf, []).

wypiszBSTbad(node(TL, D, TR), R) :-
	wypiszBSTbad(TL, LL),
	wypiszBSTbad(TR, LR),
	append(LL, [D|LR], R).

% wypiszBST(T, L) gdy L to lista zlozona z elementow drzewa BST --- z akumulatorem

wypiszBST(T, L) :- wypiszBST(T, [], L).

% wypiszBST(T, A, L) gdy L to konkatenacja wypisania T z A

wypiszBST(leaf, A, A).

wypiszBST(node(TL, D, TR), A, AL) :-
	wypiszBST(TR, A, AR),
	wypiszBST(TL, [D|AR], AL).


% stworzBST(L, T) gdy T to drzewo BST powstale z (niekoniecznie posortowanej!) listy L

stworzBST([], leaf).

stworzBST([X|L], R) :-
	stworzBST(L, T),
	insertBST(T, X, R).


% sortujBST(L1, L2) gdy lista L2 powstaje z posortowania listy L1 z uzyciem BST

sortujBST(L1, L2) :-
	stworzBST(L1, T),
	wypiszBST(T, L2).

% liscie(T, L) wtw, gdy L = lista wszystkich liści z danymi (czyli drzewa sa innej niz do tej pory!)
% drzewa typu: node(T, D, T) lub leaf(D)

liscie(T, L) :- liscie(T, [], L).

liscie(leaf(X), A, [X|A]).

liscie(node(TL, _D, TR), A, AL) :-
	liscie(TR, A, AR),
	liscie(TL, AR, AL).


% wszerz(T, L) gdy T to jakieś drzewo (niekoniecznie BST) natomiast L to jesta jego wartosci w kolejności BFS

wszerz(T, R) :-
	wszerzQ([T], [], L),
	reverse(L, R).

% wszerzQ(Q, A, L) gdy Q to kolejka (lista) drzew do obsłużenia a L to lista ich wierzchołków BFS ** akumulator

wszerzQ([], A, A).

wszerzQ([leaf|L], A, R) :-
	wszerzQ(L, A, R).


wszerzQ([node(TL, D, TR) | L], A, R) :-
	append(L, [TL, TR], TODO),
	wszerzQ(TODO, [D|A], R).



/*

(node(node(leaf, 1, node(leaf, 2, node(node(leaf, 3, leaf), 3, node(node(leaf, 4, leaf), 5, leaf)))), 6, node(leaf, 7, leaf))

===

node(
	node(
		leaf, 
	1, 
		node(
			leaf, 
		2, 
			node(
				node(
					leaf, 
				3, 
					leaf
				), 
			3, 
				node(
					node(
						leaf, 
					4, 
						leaf
					),
				 5,
			 		leaf
				)
			)
		)
	),
6, 
	node(
		leaf, 
	7, 
		leaf
	)
)


*/