smaller(tree(X, _, _), O) :- (X < O).
smaller(O, tree(X, _, _)) :- (O < X).

istree(void).
istree(tree(X, void, void)).
istree(tree(X, L, void)) :- smaller(L, X), istree(L).
istree(tree(X, void, R)) :- smaller(X, R), istree(R).
istree(tree(X, L, R)) :- smaller(L, X), smaller(X, R), istree(L), istree(R).


% test case
istree(void) % true
istree(tree(1, void, void)) % true
istree(tree(2, tree(1, void, void), void)) % true
istree(tree(2, void, tree(3, void, void))) % true

istree(tree(2, tree(3, void, void), void)) % false
istree(tree(2, void, tree(1, void, void))) % false