Prolog: Sum the values ​of the leaves in the binary tree

user_11604252 0
Viewed 600

I have a binary tree and of this binary tree I have to add the values ​​contained in the leaves, given a similar predicate:

sum_leafs ([Node, Left, Right], Sum).

I can't understand how I can do it, having to calculate the value of the leaves I should calculate the sum of the node in case both Left and Right are nil ..

[Node, nil, nil]

So I have something like:

sum_leafs([Node, Left, Right], Sum):-
    sum_leafs(Left, Sum_Left),
    sum_leafs(Right, Sum_Right),
    Sum is (Sum_Left + Sum_Right).

My attempt:

sum_leafs(nil, 0).
sum_leafs([Node, nil, nil], Node).
sum_leafs([_, Left, Right], Sum):-
    sum_leafs(Left, Sum_Left),
    sum_leafs(Right, Sum_Right),
    Sum is (Sum_Left + Sum_Right).

How can I achieve this?

Thank you

prolog
2 Answers

A list is a poor representation for a binary tree. Let's start to change that:

  • Empty tree: nil
  • Non-empty tree: t(Left,Value,Right)

Using this representation, a predicate that sums the values of the leaves can be written as:

sum_leaves(Tree, Sum) :-
    sum_leaves(Tree, 0, Sum).

sum_leaves(nil, Sum, Sum).
sum_leaves(t(nil,Value,nil), Sum0, Sum) :-
    !,
    Sum is Sum0 + Value. 
sum_leaves(t(Left,_,Right), Sum0, Sum) :-
    sum_leaves(Left, Sum0, Sum1),
    sum_leaves(Right, Sum1, Sum).

But this first version is not tail-recursive. We can improve on it:

sum_leaves(Tree, Sum) :-
    sum_leaves(Tree, 0, Sum).

sum_leaves(nil, Sum, Sum).
sum_leaves(t(nil,Value,nil), Sum0, Sum) :-
    !,
    Sum is Sum0 + Value. 
sum_leaves(t(Left,_,Right), Sum0, Sum) :-
    sum_leaves(Left, LeftSum),
    Sum1 is Sum0 + LeftSum,
    sum_leaves(Right, Sum1, Sum).
user_6346290

I have done like this:

sum_leafs(nil, 0).
sum_leafs([Node, nil, nil], Node).
sum_leafs([_, Left, Right], Sum):-
    sum_leafs(Left, Sum_Left),
    sum_leafs(Right, Sum_Right),
    Sum is (Sum_Left + Sum_Right).
user_116042520
Related