prolog need to compute the tree size

Question

I need to get the size of a tree using: size(Tree,Size)

What I have so far is wrong, please advise!

size(empty, Size).
size(tree(L, _, R), Size) :-
    size(L, Left_Size),
    size(R, Right_Size),
    Size is
        Left_Size + Right_Size + 1.

Output should produce:

?- size(node(1,2),X).
X = 2.
?- size(node(1,[2,3,4]),X).
X = 2.
?- size(node(node(a,b),[2,3,4]),X).
X = 3.

[More general solutions](http://stackoverflow.com/a/14096747/772868) are possible! — false, Jun 04 '15 at 11:08
[More efficient versions](http://stackoverflow.com/a/24715395/772868) are possible, too (with similar restricted functionality). — false, Jun 04 '15 at 11:10

CapelliC · Accepted Answer · 2015-06-04T07:36:15.433

1

Prolog is a declarative language, you must state correctly your patterns:

size(node(L,R), Size) :- ... % why you add 1 to left+right sizes ?

From the samples, I suggest to stop the recursion with Size = 1 when anything that is not a node is seen:

size(node(L,R), Size) :- !, ...
size(_, 1).

edited Jun 04 '15 at 07:36

answered Jun 04 '15 at 07:30

CapelliC

score 0 · Answer 2 · answered Dec 10 '18 at 17:21

0

size_tree(nil, 0). % nil simulates a null node

size_tree(node(Root,Left,Right), Size):-

 Root\= nil,
 RootSize = 1,
 size_tree(Left, LeftSide),
 size_tree(Right, RightSide),
 Size is (RootSize + LeftSide + RightSide).

answered Dec 10 '18 at 17:21

Shay Ribera

2 Answers2