Write a Prolog program that finds all nodes in a binary tree

Write a Prolog program that finds all nodes in a binary tree that have two non-empty children. Example: ?- my Tree (T), nonempty (T). 73 101 T = t(73, t (31, t (5, nil, nil), nil), t(101, t (83, t (97, nil, nil), nil), t (123, nil, nil))).

Solution

Binary trees are the trees where all the internal nodes have exactly 2 children.

So the question can be stated as find all the internal nodes of Binary Tree.

The code is as below. I could not run this and check. It should work

:- ensure_loaded(p4_01).

% internals(T,S) :- S is the list of internal nodes of the binary tree T.

internals(nil,[]).
internals(t(_,nil,nil),[]).
internals(t(X,L,nil),[X|S]) :- L = t(_,_,_), internals(L,S).
internals(t(X,nil,R),[X|S]) :- R = t(_,_,_), internals(R,S).
internals(t(X,L,R),[X|S]) :- L = t(_,_,_), R = t(_,_,_),
internals(L,SL), internals(R,SR), append(SL,SR,S).

% The above solution works in the flow patterns (i,o) and (i,i) without cut and produces a single correct result.
% Using a cut we can obtain the same result in a much shorter program, like this:

internals1(nil,[]).
internals1(t(_,nil,nil),[]) :- !.
internals1(t(X,L,R),[X|S]) :-
internals1(L,SL), internals1(R,SR), append(SL,SR,S).