/*  Here is a layered/inductive data type definition:
         Tree ::=  leaf  |  node(int, Tree, Tree)

    In ML, it looks like this:
         datatype Tree =  Leaf  |  Node of int * Tree * Tree

    In Prolog, you don't declare the datatype -- you just start
    using  leaf  and  node,  and the prover figures out what you
    are doing.  leaf  and  node  are "functors".
*/

/* makeTree(L, T)  asserts that  T  is an ordered tree of ints
   built from the list of ints, L   */
makeTree([], leaf).
makeTree([N|Rest], Ans) :- makeTree(Rest, T), insert(N, T, Ans).


/*  insert(N, T, U)   asserts that ordered tree  U  consists of
      ordered tree T with N inserted therein:  */
insert(N, leaf,  node(N, leaf, leaf)).

insert(N, node(M, Left, Right),  node(M, Newleft, Right))
                 :- N =< M, insert(N, Left, Newleft).

insert(N, node(M, Left, Right),  node(M, Left, Newright))
                 :- N > M, insert(N, Right, Newright).
 

/* member(N, T)  holds true when  N  is found in tree T.  */
member(N, node(N, _, _)).
member(N, node(_, Left, _)) :- member(N, Left).
member(N, node(_, _, Right)) :- member(N, Right).


/* hasElements(T, L)  asserts that  L  is a list of all
   the values stored in tree T: 
     "find all N such that  member(N, T)  holds
      and save them in list  Ans"  */
hasElements(T, Ans) :- findall(N, member(N, T), Ans).

/* try me:  ?- makeTree([3,1,5,4,2], T), hasElements(T, Elems).  */


/* Here is an ML-style definition:  
   elements(T, L)  holds true when  L  is a list of all the ints
    held within tree  T  */
elements(leaf, []).
elements(node(V, Left, Right), AnsList) :- elements(Left, L),
                                           elements(Right, R),
                                           append(L, [V], Half),
                                           append(Half, R, AnsList).
/* NOTE:  append(L1, L2, M)  is a built-in predicate
   that holds true when  M == L1 @ L2.  */

/* try me:  ?- makeTree([3,1,5,4,2], T), elements(T, Elems).  */


/* Here is an ML-style definition of  member:
   found(M, T)  asserts that  M  is found in ordered tree  T  */
found(M, node(N, Left, Right)) :-  M = N.
found(M, node(N, Left, Right)) :-  M < N, found(M, Left).
found(M, node(N, Left, Right)) :-  M > N, found(M, Right).