bintree(empty).
bintree(node(N, L, R)):- bintree(L),bintree(R).

/*
                                1
                        _______/ \_______
                       |                 |
                       2                 3
                    __/ \__          ___/ \___
                   |       |        |         |
                   4       5        6         7
                 _/ \_   _/ \_   __/ \__   __/ \__
                |     | |     | |       | |       |
                o     o o     o o       o o       o


 bintree(node(1,node(2,node(4,empty,empty),node(5,empty,empty)),node(3,node(6,empty,empty),node(7,empty,empty)))).
*/

preorder1(empty,[]).
preorder1(node(N,Left,Right),P):-
	preorder1(Left,L), preorder1(Right, R), append([N|L],R,P).
append([],L,L).
append([H|T],L, [H|M]) :- append(T,L,M).

/* Testing 1

preorder1(node(1,node(2,node(4,empty,empty),node(5,empty,empty)),node(3,node(6,empty,empty),node(7,empty,empty))),X).
   
*/


% A tail-recursive version of preorder traversal
pre(empty,A,A).
pre(node(N,Left,Right),A,D) :- 
	pre(Right,A,B),
	pre(Left,B,C),
	N.C==D.

preorder2(t,L) :- bintree(t),pre(t,[],L).


/* Testing 2
preorder2(node(1,node(2,node(4,empty,empty),node(5,empty,empty)),node(3,node(6,empty,empty),node(7,empty,empty))),X).
*/