#include <stdio.h>

// see http://cslibrary.stanford.edu/105/LinkedListProblems.pdf
// and  http://www.glenmccl.com/tip_005.htm
// and http://cslibrary.stanford.edu/105/

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

struct binarynodeWords {
	char data[81];
	struct binarynode* left;
	struct binarynode* right;
} ;


void printInorder(struct binarynode* tree) {
	if (tree != NULL) {
		printInorder(tree->left);
		printf("%3d", tree->data);
		printInorder(tree->right);
      }
}
				
struct binarynode* insertTree(struct binarynode* head, struct binarynode* node) {
	if (head == NULL) {
		head = node;
	 } 
	 else {
		struct binarynode* p = head;
		struct binarynode* back=p;
		int toRight = 0;
		int toLeft = 0;
		while ( p != NULL) {
			back = p;
			if (node->data < p->data) {
				p = p->left;
				if (p==NULL)
				toLeft = 1;
			} else {
				p = p->right;
				if (p==NULL)
					toRight = 1;
			}
		}
		if (toLeft) 
			back->left = node;
		else
			back->right = node;
	}
	return head;
}
	
int main() {
	int i;
	struct binarynode* head = NULL;
	struct binarynode* temp;
//	int vals[] = {5, 2, 8, 1, 3, 6, 15, 13, 4, 12};
	int vals[] = {5, 10, 2, 14, 10, 16, 11, 0, 19, 18};
	srand(time(0));
// add some entries to list
      for (i = 0; i < 10; i++) {
		temp = (struct binarynode*)malloc(sizeof(struct binarynode));
		//temp->data= vals[i];
		temp->data = rand() % 20;
		temp->left = NULL;
		temp->right = NULL;
		printf(" data=%d", temp->data);
		head=insertTree(head, temp);
	}
	printf("\n");

	printInorder(head);	
	printf("\n");
}