Finding the binary tree height using Prolog

Question

I am trying to code the binary tree height problem but the Prolog returns false instead of height value.

My code is :

height( nil, 0 ).
height( t(_,L, R), H ):-
   (  height(L,_)>height(R,_), height(L,H-1)
   ;  height(R,_)>=height(L,_),height(R,H-1)
   ).

A simple sample code that returns false instead of 1 is :

height(t(a,nil,nil),RES).

Thank you.

> and >= expect arithmetic expressions only. That should produce a clean error. And H-1 is a term and not an expression... — false

lurker lurker · Accepted Answer · 2014-11-23T00:14:08

height is not a function that returns the height. It is a predicate that is true when the second argument is the height of the first argument. So you can use height(L,_) > height(R,_). You have to do height(L,LH), height(R,RH) and compare LH with RH. For similar reasons, you cannot query height(L, H-1) and get expected results since, as @false points out, H-1 is the term '-'(H,1) in this context, and is not interpreted as an arithmetic expression. In Prolog, an arithmetic expression is only interpreted when it's on the right hand side of an is expression, or is in an arithmetic comparison expression.

So in full, your corrected predicate looks like:

height( nil, 0 ).         % Height of nil tree is 0
height( t(_,L,R), H ) :-  % Height of binary tree t(_,L,R) is H if...
   height(L, LH),         % LH is the height of subtree L, and
   height(R, RH),         % RH is the height of subtree H, and
   (  LH > RH             % if LH > RH, then
   -> H is LH + 1         %   H is LH + 1
   ;  H is RH + 1         % otherwise, H is RH + 1
   ).

Or more directly, you can use the max function available in Prolog (as @false points out):

height( nil, 0 ).         % Height of nil tree is 0
height( t(_,L,R), H ) :-  % Height of binary tree t(_,L,R) is H if...
   height(L, LH),         % LH is the height of subtree L, and
   height(R, RH),         % RH is the height of subtree H, and
   H is max(LH, RH) + 1.

Again, note here that an expression on the right hand side of the is will be evaluated by Prolog.

Finding the binary tree height using Prolog

1 Answers