Search code examples
prolog

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

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

Solution

  • 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).