Prolog if-else conditionals

Question

I'm new to prolog and I'm trying to implement a BST. The BST is implicit in the form of node(X,L,R) with X as an positive integer, L the left child tree, R the right child tree, and leaf as the base case.

One feature of this BST is to be able to search for an element of the tree. elem(Bst,Elem) succeeds if Elem is an element of Bst, false otherwise.

Example:

?- elem(leaf,_).
false.

?- elem(node(3,node(2,leaf,leaf),node(5,leaf,leaf)),2).
true.

My attempt at implementation:

elem(leaf,Elem) :-
  false.

elem(Bst,Elem) :-
  Bst = node(X,L,R),
  Elem > 0,
  (Elem is X ->
    true;
    elem(L,Elem),
    elem(R,Elem)).

But I'm too sure about this b/c I'm not sure what happens with the if-else conditional. The idea is obviously to succeed with true if Elem is X is true, but since prolog doesn't "return" anything, I'm not sure what would happen.

Is this right? How do I fix it? What could I do better?

Answer 1

You don't need conditionals in Prolog too often. This problem for example could be solved like this:

bst_member(node(X, L, R), Elem) :-
    compare(Order, X, Elem),
    bst_member_1(Order, Elem, L, R).

bst_member_1(>, Elem, L, _) :- bst_member(L, Elem).
bst_member_1(=, _, _, _). % Found it!
bst_member_1(<, Elem, _, R) :- bst_member(R, Elem).

This works with anything, not just integers or positive integers. If you indeed have only integers, you can use library(clpfd) and the predicate zcompare/3 instead of compare/3. But this is beyond the scope of what you are currently asking.

Answer 2

elem(node(Elem,_,_),Elem).

elem(node(X,L,R),Elem):- 
    dif(X,Elem),
    (elem(L,Elem);elem(R,Elem)).

Try this, It's as simple as I check if equal, if not, search left and right