#include<stdio.h>


typedef struct treenode * nodep;

struct treenode
{ 
    int data;
    struct treenode * left;
    struct treenode * right;
};

// abstraction constructors:

// make a new node:
nodep node(int d, nodep l, nodep r)
{
    nodep newnode;
    newnode = (nodep)malloc(12); // 12 = bytes in struct treenode
    newnode->data = d;
    newnode->left = l;
    newnode->right = r;
    return newnode;
}

// destructor - recursively deletes:
void freenode(nodep tree)
{
    if (tree != NULL)
	{
	     freenode(tree->left);
	     freenode(tree->right);
	     free(tree);
	}
}

// checks if element x is present in tree - look ma, no if-else!
int intree(int x, nodep tree)
{
  return (tree != NULL) &&
    ((x == tree->data) || intree(x,tree->left) || intree(x,tree->right));
}


// checking if a tree is a binary search tree
//...  check back later

// preorder traversal:
void preorder(nodep tree)
{
   if (tree != NULL)
       {
	   printf("%d ",tree->data);
	   preorder(tree->left);
	   preorder(tree->right);
       }
}


int main()
{
   nodep mytree = node(5,node(3,NULL,NULL),node(9,node(6,NULL,NULL),NULL));
   nodep biggertree = node(20,mytree,mytree);

   preorder(biggertree);
   //   printf("\n%d\n", isbst(mytree,neginf,posinf));
   //   printf("%d\n", isbst(biggertree,neginf,posinf));

   freenode(biggertree);     // what really happens here?
   freenode(mytree);         // and here?
   exit(0);
}


// Perhaps you're thinking, now that we have C instead of Scheme, instead
// of recursion we can now use while loops, for loops, do loops, and 
// maybe even a whole bunch of other loops.  But would you really want to?
// Try it.  If you descend through the right branch, how would you remember
// to come back and descend the left branch.  You can use a stack to keep
// track of all the nodes you have not yet completely processed, but then
// you'll just be reconstructing the recursion stack yourself.  

// In the mathematical study of computation, all computer programs are
// called "partially recursive functions" - "partial" refers to the
// fact that some programs don't terminate.  So you see, all computation
// is naturally recursive.  The only real distinction is between 
// tail and non-tail recursion.  Tail-recursion affords us an opportunity
// to optimize memory usage, a fact that's finally being widely exploited.
// The scheme language was the research platform used to study tail-recursive
// optimization.  gcc introduced it not long ago for C/C++.  Some
// Java JVMs also supports it.  Perl implementations will be required 
// to implement tail-recursive optimization in its new version 6.  
// (Note: it's harder to optimize tail-recursion in interpreted languages 
// like Java/Perl than it is for static, compilable languages such as 
// C++).

// Another point to note is that trees have the characteristic that
// their average height is O(log n), and may even be worst-case log n
// if they're balanced.  This means that even for non tail-recursive
// procedures (and even if tail-recursion is not optimized), the depth
// of recursion will be limited to a small number.  Thus recursion is 
// the logical choice for the implementation of most tree algorithms.