/* Define a few trees to work with. */ 
tree1(bt(a,
	 bt(b,nil,nil),
	 bt(c,
	    bt(d, 
	       bt(f,nil,nil),
	       bt(g,nil,nil)
	      ),
	    nil
	   )
	)
     ). 

tree2( 
      bt(a, 
	 bt(b, 
	    bt(e,nil,nil), 
	    bt(f, 
	       bt(g,nil,nil), 
	       nil
	      ) 
	   ), 
	 bt(c,nil,nil) 
        ) 
).

/*Exercice 1: X is a tree */
istree(nil).
istree(X):- X=bt(_,FG,FD),istree(FG),istree(FD).

/*Exercice 2: X is a tree having N nodes */
nnodes(nil,0).
nnodes(bt(_,Y,Z),N):- nnodes(Y,M), nnodes(Z,K), N is M+K+1.

/*Exercice 3: X is an element of T */
ismembre(X,bt(X,_,_)).
ismembre(X,T):- T=bt(_,TG,_),ismembre(X,TG).
ismembre(X,T):- T=bt(_,_,TD),ismembre(X,TD).

/*Exercice 4: L is the list of the leaves of T */
feuille(nil,[]).
feuille(bt(X,nil,nil),[X]).
feuille(bt(_,T1,T2),L):- feuille(T1,L1),feuille(T2,L2),append(L1,L2,L).

/*Exercice 5: L is the list in depth of the nodes in T*/
profondeur(nil,[]).
profondeur(bt(X,FG,FD),[X|L]):- profondeur(FG,LG), profondeur(FD,LD), append(LG,LD,L).