strom(a(a(a(nil,1,nil),2,nil),3,a(a(nil,4,nil),5,nil))).


prazdny(nil).
%neprazdny(a(_,_,_)).

%neprazdny(T) :- prazdny(T), !, fail.
%neprazdny(_) :-                true.

not1(X) :- X, !, fail. 
not1(_).

neprazdny(T) :- not1(prazdny(T)).

treeToList(nil,[]).
treeToList(a(L,X,R),V):- treeToList(L,Lx), treeToList(R,Rx), append(Lx,[X|Rx],V). 

listToTree([], nil).
listToTree(L, a(T1, X, T2)) :- append(L1,[X|L2],L), listToTree(L1,T1), listToTree(L2,T2).

rozloz([], [], []).
rozloz(T, [], T).
rozloz([X|T], [X|R1], R2) :- rozloz(T, R1, R2).

listToBT([], nil).
listToBT(L, a(T1, X, T2)) :- splitHalf2(L, L, H1, [X|H2]), listToBT(H1, T1), listToBT(H2, T2).

splitHalf([], [], []).
splitHalf(L, H1, H2) :- length(L, Len), HalfLen is Len div 2, append(H1, H2, L), length(H1, HalfLen).


splitHalf2([A|R1], [_,_|R2], [A|Res], Res2) :-
	splitHalf2(R1, R2, Res, Res2).
splitHalf2(R2, [], [], R2).
splitHalf2(R2, [_], [], R2).


select(a(L,X,R),VAL) :- A is VAL, A is X.
select(a(L,X,R),VAL) :- X < VAL, select(R,VAL).
select(a(L,X,R),VAL) :- X > VAL, select(L,VAL).