prolog is tree balanced -

i need implement predicate isbalanced/1 such isbalanced(t) true if t tree balanced.

a binary tree in case, defined structure node(left,right), left , right can either node or prolog data item.

what have far:

height(node(l,r), size) :-     height(l, left_size),     height(r, right_size),     size 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 not work, advice appreciated!

how representing tree? looks me that

• l(_) represents empty tree, and
• node(l,r) represents non-empty tree.

and suspect height/2 has bug in seem have defined height of empty tree being 1 (rather 0).

i represent binary tree follows:

• nil — empty tree

• tree(d,l,r) — non-empty tree, where

  • d: payload data
  • l: left subtree
  • r: right subtree

so 1 might represent tree

       / \   b   c     /   / \ d   e   f 

as

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

and leaf node (a tree no subtrees) looks like

tree( data , nil , nil ) 

determination of balance

so, working representation, , definition

a binary tree balanced if:

• its left sub-tree balanced
• its right sub-tree balanced
• the respective heights of sub-trees differ no more 1

we can write descriptive solution problem:

is_balanced( nil         ) .  % empty tree balanced is_balanced( tree(_,l,r) ) :- % non-empty tree balanced if ...   is_balanced(l) ,            % - left sub-tree balanced   is_balanced(r) ,            % - right sub-tree balanced   tree_height(l,lh) ,         % - height of left sub-tree   tree_height(r,rh) ,         % - height of right sub-tree   abs( lh - rh ) < 2          % - differ no more 1   .                           % right? 

we need compute height of tree.

computation of height

one can compute height of such tree follows:

tree_height( nil         , 0 ) .  % depth of empty tree zero. tree_height( tree(_,l,r) , h ) :- % non-empty tree...   tree_height( l , lh ) ,         % - compute height of left subtree   tree_height( r , rh ) ,         % - compute height of right subtree   h 1 + max( lh , rh )         % - overall height 1 more higher of 2 values obtained.   .                               % right? 

efficiency

one might note there

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

therefore, 1 might optimize things blending 2 , computing depth on fly:

edited: added wrapper predicate is_balanced/1:

is_balanced( t ) :- is_balanced( t, _ ) .  is_balanced( nil         , 0 ) .   % empty tree balanced , has height of zero. is_balanced( tree(_,l,r) , h ) :-  % non-empty tree balanced if ...   is_balanced( l , lh ) ,          % - left subtree balanced, ,   is_balanced( r , rh ) ,          % - right subtree balanced, ,    abs( lh - rh) < 2 ,              % - respective heights differ no more 1, ,   h 1 + max( lh , rh )          % - current tree's height 1 more larger of heights of 2 subtrees.   .                                % easy! (and elegant!)