/***********************************************************
  Author  : Yan Huang 
  Date    : 02.18.07
  Synopsis: insertion and inorder traversal
            of a simple character based binary search tree
***********************************************************/

#include <string>
#include <iostream>

struct TreeNode {
   char item;         // The data in this node.
   TreeNode *left;   // Pointer to the left subtree.
   TreeNode *right;  // Pointer to the right subtree.
};


/* a recursive insertion function, returns 1 if the node already exists*/
/* only works after the root is not NULL*/
int insert(TreeNode * current_node, char c){

   if (current_node == NULL) return 0;
   if (current_node->item == c) return 1;

   if (current_node->item > c) /* c belongs to the left of current node*/{
         if (current_node->left) {
             current_node = current_node->left;
             insert(current_node,c); 
         } else {
              TreeNode *newNode = new TreeNode;
              newNode->item = c;
              newNode->left = NULL;
              newNode->right= NULL;
              current_node->left = newNode;
           }
     } else { /* c belongs to the right side of current node*/
         if (current_node->right) {
             current_node = current_node->right;
             insert(current_node,c);
         } else {
              TreeNode *newNode = new TreeNode;
              newNode->item = c;
              newNode->left = NULL;
              newNode->right= NULL;
              current_node->right= newNode;
           }
 
       }

};


void inOrder(TreeNode *current_node){

     if (current_node == NULL) return;
       else {
                 inOrder(current_node->left);
                 cout << current_node->item << " ";
                 inOrder(current_node->right);
                 
            } 
     
};

void main(){
   
   TreeNode *root = NULL, current_node;

   root = new TreeNode;
   root->item = 'C';
   root->left = NULL;
   root->right= NULL;
    

   insert(root, 'D');

   inOrder(root); cout << endl;

   insert(root, 'A');
   inOrder(root); cout << endl;

   insert(root, 'F');
   inOrder(root); cout << endl;

   insert(root, 'B');
   inOrder(root); cout << endl;
       
}