/* Predicates represent atomic logical statements about their arguments:
   e.g.,  pred(X1,X2,Xn). Predicates can be true or false. 
   Terms represent functions that map arguments into an individual: e.g.,
   funct(X1,X2,...,Xn) maps to different entities (depending on X1,X2,...,Xn). 
   Terms can be used inside predicates as arguments of predicates.
   We can use terms also with the equality "=", e.g.: not(X = term(Y,Z) )
   Names of the predicates and terms are up to you, the programmer, but once
   you have decided what your predicates and terms mean, you have to use same
   meaning everywhere in your program. 
   Terms help to represent structured data: in many cases they are more
   convenient than lists.
   
   Example: we can use term with 3 arguments 
		tree(Element,LeftBranch,RightBranch)
   to represent a binary tree. The empty tree can be represented by 
   the constant "void". The tree
                     a
                    / \
                   b   c
   can be represented as    tree(a, tree(b, void, void), tree(c,void,void))
   
   It is important to realize that binary tree is a recursive data structure:
   a sub-tree of a tree is a tree itself. In particular, if we consider the root
   of the tree, then its left child is a root of a left sub-tree, which is also
   a tree. Similarly, its right child is a root of a right sub-tree, which is
   also a binary tree. Below, we see that all recursive programs take advantage
   of recursiveness of binary trees.
*/


/* The predicate  binaryTree(X) is true if X is a binary tree  */

binaryTree(void).
binaryTree( tree(Element,Left,Right) ) :- 
                    binaryTree(Left), binaryTree(Right).


/* The predicate  memberOfTree(Elelment,X) is true if Element is a member of
   a binary tree X. To implement this predciate we do case analysis.  */

memberOfTree(Element, tree(Root,Left,Right) ) :- Element=Root.
/* memberOfTree(Element, tree(Element,Left,Right) ). */

memberOfTree(Element, tree(Node,Left,Right) ) :- memberOfTree(Element,Left).

memberOfTree(Element, tree(Node,Left,Right) ) :- memberOfTree(Element,Right).


/* Exercise. Implement the predicate  treeToList(X,List), where X is a given 
   ordered non-empty binary tree, and List is an ordered list of elements in nodes 
   of the tree. Recall that in ordered tree (known also as a binary search tree)
   all elements on the left are less than the root, but all elements on the right
   are greater than the root (see Wikipedia).  Example:
                4
               / \
             2     6
            / \   / \ 
           1   3  5  7
   is an ordered tree given as an input to predicate  "treeToList".
   Your program must compute the list [1,2,3,4,5,6,7].
*/

treeToList(X,List) :- binaryTree(X), convert(X,List).

/* The helping predicate convert(X,List) is true if X is a given non-empty tree, 
   and List is a representation of this tree as an ordered list. */

convert( tree(Element,void,void), List) :- List=[Element].    /* Leaf in a tree */


/* Write the recursive rule */

convert( tree(Root,Left,Right), List) :- 
     

/* To test your implementation, start Prolog, consult your program
and ask the query  ? - example(L).
*/

example(List) :- treeToList( tree(4, 
              tree(2,tree(1,void,void),tree(3,void,void)), 
              tree(6,tree(5,void,void),tree(7,void,void))), List).


