prolog is tree balanced

Question

I need to implement a predicate isBalanced/1 such that isBalanced(T) is true if T is a tree that is balanced.

A binary tree is in this case, defined by the structure node(left,right), where left and right can be either another node or any Prolog data item.

What I have so far:

height(node(L,R), Size) :-
    height(L, Left_Size),
    height(R, Right_Size),
    Size is Left_Size + Right_Size + 1 .
height(l(_),1).

isBalanced(l(_)).
isBalanced(node(B1,B2)):-
    height(B1,H1),
    height(B2,H2),
    abs(H1-H2) =< 1,
    isBalanced(B1),
    isBalanced(B2).

Expected output:

?- isBalanced(1).
true.
?- isBalanced(node(1,2)).
true.
?- isBalanced(node(1,node(1,node(1,2)))).
false.

It does not work, any advice will be greatly appreciated!

In your [first question](http://stackoverflow.com/q/30636790/772868), you had `size(empty, Size).` But now you say `height(_,1)`. Do you mean by that thateverything is of height one? You rather mean only `height(l(_),1`)`. — false, Jun 04 '15 at 12:15
Also note that `height` assumes a tree with `node/2` terms, whereas `isBalanced/1` assumes a tree with `b/1` terms. They are incompatible, so your queries will either fail or loop (provided `height(_,1)` has been corrected). — false, Jun 04 '15 at 12:16
A binary tree is balanced if, at every node, the difference between the number of leaves appearing in the left and right subtree is at most one. (A tree which contains just one leaf is considered balanced.) — Zast, Jun 04 '15 at 12:31
Right! But nevertheless `b/2` and `node/2` just don't unify! — false, Jun 04 '15 at 12:33
replace `b(` by `node(` ; and add `l(_)` to the fact of `height/2`. — false, Jun 04 '15 at 12:39

Nicholas Carey · Answer 1 · 2015-06-05T17:11:27.310

How are you representing your tree? It looks to me that

l(_) represents the empty tree, and
node(L,R) represents a non-empty tree.

And I suspect that your height/2 has a bug in that you seem to have defined the height of an empty tree as being 1 (rather than 0).

I would probably represent a binary tree as follows:

nil — the empty tree
tree(D,L,R) — a non-empty tree, where
- D: payload data
- L: left subtree
- R: right subtree

so that one might represent the tree

    a
   / \
  b   c   
 /   / \
d   e   f

as

tree( a ,
  tree( b ,
    tree( d , nil , nil ) ,
    nil
  ) ,
  tree( c ,
    tree( e , nil , nil ) ,
    tree( f , nil , nil ) 
) .

and a leaf node (a tree with no subtrees) looks something like

tree( data , nil , nil )

Determination of Balance

So, working from that representation, and from the definition

A binary tree is balanced if:

Its left sub-tree is balanced

Its right sub-tree is balanced

The respective heights of the sub-trees differ by no more than 1

We can easily write a descriptive solution to the problem:

is_balanced( nil         ) .  % the empty tree is balanced
is_balanced( tree(_,L,R) ) :- % a non-empty tree is balanced IF ...
  is_balanced(L) ,            % - the left sub-tree is balanced
  is_balanced(R) ,            % - the right sub-tree is balanced
  tree_height(L,LH) ,         % - the height of the left sub-tree
  tree_height(R,RH) ,         % - the height of the right sub-tree
  abs( LH - RH ) < 2          % - differ by no more than 1
  .                           % Right?

We just need to compute the height of a tree.

Computation of Height

One can compute the height of such a tree as follows:

tree_height( nil         , 0 ) .  % the depth of an empty tree is zero.
tree_height( tree(_,L,R) , H ) :- % for a non-empty tree...
  tree_height( L , LH ) ,         % - we compute the height of the left subtree
  tree_height( R , RH ) ,         % - we compute the height of the right subtree
  H is 1 + max( LH , RH )         % - the overall height is 1 more than the higher of the two values thus obtained.
  .                               % Right?

Efficiency

One might note that there

seems to be a lot of tree traversals happening, and
is_balanced/2 has a suspicious resemblance to tree_height/2.

Therefore, one might optimize things by blending the two and computing depth on the fly:

Edited: Added wrapper predicate is_balanced/1:

is_balanced( T ) :- is_balanced( T, _ ) .

is_balanced( nil         , 0 ) .   % the empty tree is balanced and has a height of zero.
is_balanced( tree(_,L,R) , H ) :-  % a non-empty tree is balanced IF ...
  is_balanced( L , LH ) ,          % - its left subtree is balanced, and
  is_balanced( R , RH ) ,          % - its right subtree is balanced, and 
  abs( LH - RH) < 2 ,              % - their respective heights differ by no more than 1, and
  H is 1 + max( LH , RH )          % - the current tree's height is 1 more than the larger of the heights of the two subtrees.
  .                                % Easy! (And elegant!)

Thanks, I especially like the optimized version. However, what I need is a predicate that takes just one input, also note that neither of your answers return true for `isBalanced(1).`, which is the requirement for my task. — Zast, Jun 05 '15 at 04:28
You shouldn't need to include anything: [`max/2`](http://www.swi-prolog.org/pldoc/man?function=max/2) is a built-in ISO arithmetic function. You should be able to say `X is max(3*2,4*5).` and get back `X = 20`. But something like `( X > Y -> Z = X ; Z = Y )` should unify Z with the larger of `X` and `Y`. — Nicholas Carey, Jun 05 '15 at 17:11
Also, see my amended answer that includes a wrapper predicate `is_balanced/1`. — Nicholas Carey, Jun 05 '15 at 17:12
I still get the wrong answer from your solution. It asks if I want to `Correct to: "is_balanced(1)"?`, if I select yes, it returns false, which is not the answer I need it to be true. If I select no, is really spits the dummy and causes an exception! `1 ?- isBalanced(1). Correct to: "is_balanced(1)"? yes false. 2 ?- isBalanced(1). Correct to: "is_balanced(1)"? no ERROR: residue_vars/2: Undefined procedure: isBalanced/1 ERROR: However, there are definitions for: ERROR: is_balanced/1 ERROR: is_balanced/2 Exception: (7) isBalanced(1) ? abort % Execution Aborted 3 ?- ` — Zast, Jun 06 '15 at 00:30

prolog is tree balanced

1 Answers1