prolog recursively find largest node

Question

Just a simple binary tree and i want to find the the largest node.
example tree: t(t(t(nil,1,nil),2,t(nil,3,nil)),4,t(t(t(nil,8,nil),5,nil),6,t(nil,7,nil)))

int L(t,max) {
if(t=null) return max;
if(max<t.root) max = t.root;
LN(t,max);
RN(t,max);
return max;
}
L(tree,tree.root);

I just cant wrap my head around applying it to prolog. Here i display each node. Which i get, but i dont understand how to save the max value and keep it recursively.

tree(nil).
tree(t(L,Root,R)) :- 
    tree(L),
    tree(R), 
    write(Root).

edit: It checks all the leaf nodes, but ignores the t(nil,8,nil)

tree(nil,0).
tree(t(nil,Q,nil),Q) :- !.
tree(t(nil,Q,_),Q).
tree(t(_,Q,nil),Q).
tree(t(L,_,R),Max) :- 
    tree(L, LValue),
    tree(R, RValue), 
    max(LValue,RValue,Max).

I noticed in a comment below you'd figured it out. It would be great if you could answer your own question here. — Rich

mercator mercator · Accepted Answer · 2008-11-25T20:56:58

Is this another homework assignment?

In any case, I'll try to let you do the thinking since you seem to be learning Prolog. Not to mention the fact that I don't actually have Prolog running on my computer, so I couldn't be sure my suggested solution would actually work.

The fact that the 5 is the only node with only one subnode (i.e. the 8 it's ignoring) should tell you something. All the other nodes are either leaf nodes or have two subnodes.

What exactly is it that you think these two rules do?

tree(t(nil,Q,_),Q).
tree(t(_,Q,nil),Q).

prolog recursively find largest node

1 Answers