----------------------
Check if a tree is BST
----------------------

checkIfBST(t(_, nil, nil)).

checkIfBST(t(Key, t(LKey, LLT, LRT), nil)):-
    Key > LKey,
    checkIfBST(t(LKey, LLT, LRT)).

checkIfBST(t(Key, t(RKey, RLT, RRT))):-
    Key > RKey,
    checkIfBST(t(RKey, RLT, RRT)).

checkIfBST(t(Key, t(LKey, LLT, LRT), t(RKey, RLT, RRT))):-
    Key > LKey,
    Key < RKey,
    checkIfBST(t(LKey, LLT, LRT)),
    checkIfBST(t(RKey, RLT, RRT)).


-------------------
BUILD BST FROM LIST
-------------------

addTree(A, t(Key, nil, R), t(Key, t(A, nil, nil), R)):-
    A < Key, !.

addTree(A, t(Key, L, nil), t(Key, L, t(A, nil, nil))):-
    A > Key, !.

addTree(A, t(Key, L, R), t(Key, NL, R)):-
    A < Key, !,
    addTree(A, L, NL).

addTree(A, t(Key, L, R), t(Key, L, NR)):-
    A > Key, !,
    addTree(A, R, NR).

buildBST(L, R):-
    buildBST(L, [], R).

buildBST([], R, R).

buildBST([H|T], [], R):-
    buildBST(T, t(H, nil, nil), R).

buildBST([H|T], t(X, L, R), Res):-
    addTree(H, t(X, L, R), Res1),
    buildBST(T, Res1, Res).