/* tree.c */
/* simplified binary tree search */

#include <stdio.h>

#define TRUE 1
#define FALSE 0

struct tree {
	int val;
	struct tree *lt,*gt;
};

int search(struct tree *root, int v)
{
	if (root == NULL)        
		return(FALSE);
	else if (v == root->val) 
		return(TRUE);
	else if (v < root->val)  
		return(search(root->lt,v));
	else                     
		return(search(root->gt,v));
}

struct tree *bput(struct tree *root, int v)
{
	struct tree *x;

	if (root == NULL) {
		x = (struct tree *)malloc(sizeof(struct tree));
		x->val = v;
		x->lt  = NULL;
		x->gt  = NULL;
		return (x);
	} else {
		if (v < root->val) {
			if (root->lt==NULL) 
				root->lt = bput(root->lt,v);
			else                
				(void)bput(root->lt,v);
		} else {
			if (root->gt==NULL) 
				root->gt = bput(root->gt,v);
			else                
				(void)bput(root->gt,v);
		}
	}
}

main()
{
	struct tree *root;
	int i;

	root=bput(NULL,5);
	printf("%ld\n",(long)root);
	bput(root,8);bput(root,3);bput(root,4);
	for (i = 1; i < 10; i++) {
		printf("%d %d\n",i,search(root,i));
	}
}