Prolog binary tree node value count

0
votes

Can anyone help me how to realize predicate in Prolog which counts the all the node numbers of a binary tree?

For example:

tree1(tree(1,
        tree(2,
            tree(3,nil,nil),
            tree(4,nil,nil)),
        tree(5,
            tree(6,nil,nil),
            tree(7,nil,nil))
    )
).

Would return 28. Anyone can help?

1
prolog
Are you sure about 23? Looks like 28 to me, or I am misunderstanding the question. – user1812457
My mistake, it was 28 – John

1 Answers

1
votes

The trivial recursive solution. Not tail-recursive.

treesum(nil, 0).
treesum(tree(X,T1,T2), S) :-
    treesum(T1, S1), treesum(T2, S2),
    S is X+S1+S2.