Given two binary trees T1 and T2 having the same height, I would like to know how to check if the number of nodes of T1 is equal to the number of nodes in T2, for each value of depth D.
I wrote a predicate numberOfNodesatD(T, N, D) which calculates the number of nodes at a depth D, but I am not able to define in Prolog the equality between the number of nodes if N1 == N2.
Riffing off my answer to your earlier question, Prolog - Find the depth of an element in a binary tree,
We can use
visit(T,P,D) :- visit(T,0,P,D) .
visit( t(_,L,_) , N, P, D ) :- N1 is N+1, visit(L,N1,P,D) .
visit( t(P,_,_) , D, P, D ) .
visit( t(_,_,R) , N, P, D ) :- N1 is N+1, visit(R,N1,P,D) .
and do something like this:
node_count_by_depth(T,D,N) :-
findall( D, visit(T,_,D), Ds ) ,
msort(Ds,Ss)l ,
groups(Ss,Fs) .
groups( [] , [] ) .
groups( [X|Xs] , Ys ) :- groups(Xs, X:1, Ys ).
groups( [] , Y:N , [Y:N] ) . % the end of the source list is a sequence break.
groups( [X|Xs] , X:N , Ys ) :- % if we haven't hit a sequence break...
N1 is N+1 , % - increment the count
groups(Xs,X:N1,Ys) . % - and recurse down
groups( [X|Xs] , Y:N , [Y:N|Ys] ) :- % otherwise...
X \= Y , % - we have hit a sequence break,
groups(Xs,X:1,Ys) % - recurse down, having moved the tuple to the result list
. % Easy!
And once you have that, then it's a matter of:
same_number_of_nodes_at_depth(T1,T2,D,N) :-
node_count_by_depth(T1,L1),
node_count_by_depth(T2,L2),
member( D:N, L1 ),
member( D:N, L2 ).