My predicate to calculate the depth of a binary tree branch isn't working

user_9793905 0
Viewed 36

I'm trying to calculate the depth of the left branch in binary trees but the predicate keeps failing!

I've tried trace. and I've arrived to the conclusion that the fail status must come from the is\2 functor, but I still can't figure out what the problem is...

leftdepth(void,0).
leftdepth(tree(_,Left,_),N):-leftdepth(Left,N),N is N+1.

I expect the output of the query leftdepth(tree(3,tree(2,tree(5,void,void),tree(7,void,void)),void),3). to be true, but it outputs false.

depth prolog
1 Answers

The call:

N is N + 1.

does not make much sense. In Prolog a variable can be unified with a value, but you then can no longer "re-unify" it with a different value. One of the concepts of declarative programming is that variables can not change value.

What you can do is create an extra variable, one thus for the level of the "child", and one for the level of the "parent":

leftdepth(void, 0).
leftdepth(tree(_,Left,_), N1):-
    leftdepth(Left, N),
    N1 is N+1.
user_675790
Related