Example of a Binary Tree

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

// our data structure (a binary tree node)
typedef struct node{
	int data;
	struct node* left;
	struct node* right;
} node;


// initializes a node struct
node* newNode(int data){
	node *node;
	node = malloc(sizeof(node));
	if (node != NULL){
		node->data = data;
		node->left = NULL;
		node->right = NULL;
	}
	return(node);
}


// inserts a node into the btree
node* insert(node *node, int data){
	if(node == NULL) {
		return (newNode(data));	
	}else{
		if(data <= node->data){
			node->left = insert(node->left, data);
		}else{
			node->right = insert(node->right, data);
		}
	}
	return (node);
}

// retreives a node, by it's data
int lookup(node *node, int target) {
	if(node == NULL){
		return 0;
	}else{
		if(target == node->data){
			return 1;
		}else{
			if (target < node->data){
				return (lookup(node->left, target));
			}else{
				return (lookup(node->right, target));
			}			
		}
	}
}

// prints each item in the btree
void traverse(node *node){
	if(node == NULL){
		return;
	}

	printf("data: %i\n", node->data);

	if(node->left){
		traverse(node->left);
	}

	if(node->right){
		traverse(node->right);
	}
}


// releases the entire btree
void empty(node *node){
	if(node == NULL){
		return;
	}
	
	if(node->left){
		empty(node->left);
	}

	if(node->right){
		empty(node->right);
	}

	printf("releasing item %i\n", node->data);
	free(node);
}



int main(int argc, char *argv[], char *env[]){
	node *root_node;
	root_node = insert(NULL, 5);
	insert(root_node,7);
	insert(root_node,2);
	insert(root_node,1);
	insert(root_node,10);

	printf("3 is in the btree: %s\n", (lookup(root_node,3) == 1 ? "YES" : "NO"));
	printf("2 is in the btree: %s\n", (lookup(root_node,2) == 1 ? "YES" : "NO"));


	traverse(root_node);

	empty(root_node);
	
	return 0;
}