Path in binary tree - Prolog

Question

I have a problem with this homework. I have to write code in prolog which will show me deepest way to the leaf of the tree.

Tree is represented as:

tree([ [ [],r,[[],u,[[],t,[]]]  ], a ,  [ [], c, [] ]])

Where is [ ] like nil and a is a root.

It should have show me something like this: PATH = [a, r, u, t]

I will be very thankful.

Solution:

deepest(T,D) :- aggregate(max(L,P),(path(T,P),length(P,L)),max(_,D)).

path([],[]).
path([L,K,R],[K|P]) :- path(L,P) ; path(R,P).

Test:

?- tree(T),deepest(T,P).
T = [[[], r, [[], u, [[], t|...]]], a, [[], c, []]],
P = [a, r, u, t].

Answer 1

I know, we should not do HWs... but this solution - as is - will probably not be adeguate for your class. Anyway, hope it will help you how to tackle such kind of problems in Prolog.

deepest(T,D) :- aggregate(max(L,P),(path(T,P),length(P,L)),max(_,D)).

path([],[]).
path([L,K,R],[K|P]) :- path(L,P) ; path(R,P).

test:

?- tree(T),deepest(T,P).
T = [[[], r, [[], u, [[], t|...]]], a, [[], c, []]],
P = [a, r, u, t].

note: after you grasp the basic of this language, usually no debug is required. The solution is declarative enough...

Answer 2

Since this is a homework, I won't give you the solution straight away.

First, let's have a look at your tree structure. When you look at the tree, you can see one of two options: either it would be a nil represented as [], or it will be a node with a value and two subtrees [LeftSubTree, Value, RightSubTree]. Your predicate should therefore have two clauses for the two cases.

In these two cases, what is the deepest path? Well, for nil the answer is easy: there are no nodes, therefore the longest path is actually an empty list.

For a tree node that is not a nil, what will the longest path look like? It will start with with value in current node and continue to either left or right subtree, depending on which is deeper. Thus to get a deepest path from a node, compute the deepest path recursively in the left and right subtree, take the longer of them and plop value from current node in the front.

To implement it this way, you will find it very convenient to have a helper predicate longer(List1, List2, LongerList) that will put the longer of List1 and List2 into LongerList.

Answer 3

Here's a pure variant that doesn't require all-solution meta-predicates like aggregate/3.

First, here's your sample tree again:

sampleTree([[[],r,[[],u,[[],t,[]]]],a,[[],c,[]]]).

Next, is_tree/1 defines what trees look like:

is_tree([]).
is_tree([Left,_,Right]) :-
   is_tree(Left),
   is_tree(Right).

Finally, we define tree_leftmostLongestPath/2 which we use for pre-order tree traversal.

Compared to is_tree/1, tree_leftmostLongestPath_/4 has 3 additional arguments:

• RPath which is the path so far in reversed order
• Best0 is a pair Len-Path and holds the longest path found so far
• Best also is a pair Len-Path and holds the longest path of the entire tree/subtree

Here's the code:

:- use_module(library(clpfd)).

tree_leftmostLongestPath(Tree, Path) :-
   tree_leftmostLongestPath_(Tree, [], 0-[], _-Path).

% "internal" auxiliary predicate
tree_leftmostLongestPath_([], RPath, Best0, Best) :-
   Best0 = L0-_,
   length(RPath, Len),
   (  Len #=< L0,                       Best = Best0
   ;  Len #>  L0, reverse(RPath, Path), Best = Len-Path
   ).
tree_leftmostLongestPath_([Left,Name,Right], RPath, Best0, Best) :-
   RPath1 = [Name|RPath],
   tree_leftmostLongestPath_(Left , RPath1, Best0, Best1),
   tree_leftmostLongestPath_(Right, RPath1, Best1, Best).

Some queries and answers:

?- sampleTree(Tree), tree_leftmostLongestPath(Tree, Path).
Path = [a,r,u,t], Tree = [[[],r,[[],u,[[],t,[]]]],a,[[],c,[]]]).

?- is_tree(Tree), tree_leftmostLongestPath(Tree, Path).
   Path = []     , Tree = []
;  Path = [A]    , Tree = [[],A,[]]
;  Path = [A,B]  , Tree = [[],A,[[],B,[]]]
;  Path = [A,B,C], Tree = [[],A,[[],B,[[],C,[]]]]
…