prolog in math - searching the level of node in prolog

Assuming here is a binary search tree, and given the rule that above(X,Y) - X is directly above Y. Also I created the rule root(X) - X has no parent.

Then, I was trying to figure out what the depth of node in this tree. Assume the root node of tree is "r" So I got fact level(r,0). In order to implement the rule level(N,D) :-, what I was thinking is it should be have a recursion here. Thus, I tried

level(N,D): \+ root(N), above(X,N), D is D+1, level(X,D).

So if N is not a root, there has a node X above N and level D plus one, then recursion. But when I tested this, it just works for the root condition. When I created more facts, such as node "s" is leftchild of node "r", My query is level(s,D). It returns me "no". I traced the query, it shows me

  1    1  Call: level(s,_16) ? 
  1    1  Fail: level(s,_16) ?

I just confusing why it fails when I call level(s,D)?

Solution

There are some problems with your query:

In Prolog you cannot write something like D is D+1, because a variable can only be assigned one value;
at the moment you call D is D+1, D is not yet instantiated, so it will probably cause an error; and
You never state (at least not in the visible code) that the level/2 of the root is 0.

A solution is to first state that the level of any root is 0:

level(N,0) :-
    root(N).

Now we have to define the inductive case: first we indeed look for a parent using the above/2 predicate. Performing a check that N is no root/1 is not necessary strictly speaking, because it would conflict with the fact that there is an above/2. Next we determine the level of that parent LP and finally we calculate the level of our node by stating that L is LP+1 where L is the level of N and LP the level op P:

level(N,L) :-
    above(P,N),
    level(P,LP),
    L is LP+1.

Or putting it all together:

level(N,0) :-
    root(N).
level(N,L) :-
    above(P,N),
    level(P,LP),
    L is LP+1.

Since you did not provide a sample tree, I have no means to test whether this predicate behaves as you expect it to.

About root/1

Note that by writing root/1, you introduce data duplication: you can simply write:

root(R) :-
    \+ above(_,R).