CODEWITHSUNDEEP
treeprologheightbinary-tree
Khrn
Khrn

Reputation: 342

Height of a tree - PROLOG

I try to write a predicate to find the height of a tree in Prolog.

My tree is represented like this: 

             A
           /    \
          B      C
         / \    / \
        D   E  F   G

[a,[b,[d,e],c[f,g]]] ([Root,[Children]])

My predicate is:

height(Tr,0) :- 
   atomic(Tr).
height([L|R],N) :- 
   height(L,N1),
   height(R,N2), 
   N is max(N1,N2)+1.

But my code doesn't work. When I write :

height([a,[b,[d,e],c,[f,g]]],N).

N equals 8.

Can I have some help please ?

NB: The height of the root begins at 0.

Upvotes: 2

Views: 2970

Answers (2)

CapelliC
CapelliC

Reputation: 60024

Your query doesn't seem to represent a valid tree, that should always have the shape [_, SubList]. This snippet assumes such representation, and availability of library(aggregate):

height([_,Sub], Height) :- !,
    aggregate(max(H + 1), S^(member(S, Sub), height(S, H)), Height).
height(_, 0).

yields

?- height([a,[ [b,[d,e]], [c,[f,g]] ]],N).
N = 2.

Upvotes: 0

Nicholas Carey
Nicholas Carey

Reputation: 74287

It helps to find the right abstraction.

Given a binary tree represented using these conventions:

  • An empty tree is denoted by the atom nil.
  • A non-empty tree is denoted by the structure tree/3, where
    • the 1st argument is the node's payload,
    • the 2nd argument is the left subtree (nodes whose payload collates as less than that of the current node),
    • the 3rd argument is the right subtree (nodes whose payload collates as greater than that of the current node)

The solution is pretty simple:

tree_depth( nil         , 0 ) .   % the depth of an empty tree is 0.
tree_depth( tree(_,L,R) , D ) :-  % the depth of a non-empty tree is computed thus:
  tree_depth(L,L1) ,              % - compute the depth of the left subtree
  tree_depth(R,R1) ,              % - compute the depth of the right subtree
  D is 1 + max(L1,R1)             % - the overall depth is 1 more than the maximum depth in both subtrees.
  .                               %

Computing the depth of a n-ary tree where each node can have an arbitrary number of children, isn't much more complicated. We'll represent our n-ary tree thus:

  • The empty tree is again denoted by the atom nil.
  • A non-empty tree is denoted by a structure tree/2, where
    • the 1st argument is the node's payload
    • the 2nd argument is a list containing the node's subtrees (any of which might be nil).

The solution is, again, simple:

tree_depth( nil       , 0 ) .   % the depth of the empty tree is 0.
tree_depth( tree(_,C) , D ) :-  % the depth of a non-empty tree is computed thus:
  subtree_depth( C , 0 , T ) ,  % - compute the depth of the subtrees of the current node
  D is 1+T                      % - add 1 to that
  .                             %

subtree_depth( []     , D , D ) .   % child subtrees exhausted? unify the accumulator with the result
subtree_depth( [X|Xs] , T , D ) :-  % otherwise...
  tree_depth(X,X1) ,                % - compute the depth of the current subtree
  T1 is max(T,X1) ,                 % - set the accumulator the max value
  subtree_depth( Xs , T1 , D )      % - recurse down on the tail.
  .

Upvotes: 2

Related Questions