Prolog, binary tree

Question

I want to find the deepest element of a binary tree, So far the code only works for empty tree or the height is one.

Here is the code My height function works correctly.

deepest(node(L,X,R),X):- height(L,0),height(R,0).
deepest(node(L,_,R),X):- height(L,D1),height(R,D2), D1 > D2,  deepest(L,X).
deepest(node(L,_,R),X):- height(L,D1),height(R,D2), D1 =< D2, deepest(R,X).

edit: example

?- deepest(node(node(node(leaf,8,leaf),20,leaf),
                      30,
                      node(node(leaf,88,leaf),33,node(leaf,888,leaf))),
                 X).
X = 8 ;
X = 88 ;
X = 888 ;
false.

It looks fine to me, at least to get the first result. It may have problems with the backtracking. What happens if you change the first rule to deepest(node(leaf,X,leaf),X).? — NotAUser
– NotAUser, Commented Oct 12, 2012 at 17:07

CapelliC · Accepted Answer · 2012-10-12 08:25:37Z

1

I suspect the relation height (btw there are not functions in Prolog), will be useless for the task, because it forgets the essential info required.

deepest(T, E) :-
    deepest(T, E, _).

deepest(node(L, X, R), E, D) :-
    deepest(L, EL, DL),
    deepest(R, ER, DR),
    (   DL > DR
    ->  E = EL, D is DL + 1
    ;   (   DL < DR
        ->  E = ER, D is DR + 1
        ;   (   DL > 0  % DL & DR are equals
            ->  E = L, D is DL % deepest is arbitrary here
            ;   E = X, D is 1
            )
        )
    ).
deepest(N, N, 0).

edit for intended data structure, instead of deepest(N, N, 0). I think it's clearer to use

deepest(_, _, 0).

edited Oct 12, 2012 at 8:25

answered Oct 12, 2012 at 6:33

CapelliC

60.1k5 gold badges50 silver badges94 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

user206428 · Accepted Answer · 2012-10-14 06:08:38Z

Here's an alternate version which makes use of some basic built-ins, namely append/3, keysort/2, reverse/2, and maplist/3:

deepest(Tree, N) :-
    deepest(Tree, 0, NL),
    maplist(strip_key, NL, N).

deepest(leaf, _, []). 
deepest(node(L, X, R), D, [DN-N|Res]) :-
    NewD is D + 1,
    deepest(L, NewD, LL), 
    deepest(R, NewD, RL),
    append([D-X|LL], RL, NL),
    keysort(NL, KL),
    reverse(KL, [DN-N|Rem]),
    first_key_run(Rem, DN, Res).

first_key_run([DN-N|Rem], DN, [DN-N|NL]) :-
    !, 
    first_key_run(Rem, DN, NL).
first_key_run(_, _, []).

strip_key(_K-V, V).

This version builds up a list of Depth-Node items at every node in the tree, performs keysort/2 to the list which orders them shallowest-first (O(N·log(N)), reverses the order (O(N)), then keeps the first run of equal-deepest nodes (O(N)).

This version also computes exactly the number of nodes at equal-deepest depth. For example:

?- deepest(node(node(node(leaf,8,leaf),20,leaf),30,node(node(leaf,88,leaf),33,node(leaf,888,leaf))), X).
X = [88, 888, 8].

Collectives™ on Stack Overflow

Prolog, binary tree

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related