BinarySearchTree.c

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

typedef struct node_s node_t;

typedef struct node_s {
	int data;
	node_t* left;
	node_t* right;
} node_t;

void Free( node_t* root ) {
	if( root == NULL ) {
		return;
	}
	Free( root->left );
	Free( root->right );
	free( root );
}

int Left_Of( const int value, const node_t* root ) {
	return value < root->data;
}

int Right_Of( const int value, const node_t* root ) {
	return value > root->data;
}

node_t* Insert( node_t* root, const int value ) {
	if( root == NULL ) {
		node_t* node = malloc( sizeof( node_t ) );
		node->left = NULL;
		node->right = NULL;
		node->data = value;
		return node;
	}
	if( Left_Of( value, root ) ) {
		root->left = Insert( root->left, value );
	} else if( Right_Of( value, root ) ) {
		root->right = Insert( root->right, value );
	}
	// else: root->data == value
	return root;
}

int Search( const node_t* root, int value ) {
	if( root == NULL ) {
		return 0;
	}
	if( Left_Of( value, root ) ) {
		return Search( root->left, value );
	}
	if( Right_Of( value, root ) ) {
		return Search( root->right, value );
	}
	// else: root->data == value
	return 1;
}

int Leftmost_Value( const node_t* root ) {
	while( root->left != NULL ) {
		root = root->left;
	}
	return root->data;
}

node_t* Delete( node_t* root, int value ) {
	if( root == NULL ) {
		return root;
	}
	if( Left_Of( value, root ) ) {
		root->left = Delete( root->left, value );
	} else if( Right_Of( value, root ) ) {
		root->right = Delete( root->right, value );
	} else {
		// root->data == value, delete this node
		if( root->left == NULL ) {
			node_t* newRoot = root->right;
			free( root );
			return newRoot;
		}
		if( root->right == NULL ) {
			node_t* newRoot = root->left;
			free( root );
			return newRoot;
		}
		root->data = Leftmost_Value( root->right );
		root->right = Delete( root->right, root->data );
	}
	return root;
}

int main() {
	node_t* root = NULL;
	root = Insert( root, 5 );
	root = Insert( root, 7 );
	root = Insert( root, 9 );
	root = Insert( root, 8 );
	root = Insert( root, 6 );
	root = Insert( root, 4 );

	printf( "Contains 9: %d\n", Search( root, 9 ) );
	printf( "Contains 2: %d\n", Search( root, 2 ) );

	root = Delete( root, 7 );
	root = Delete( root, 5 );
	root = Delete( root, 4 );

	printf( "Contains 9: %d\n", Search( root, 9 ) );
	printf( "Contains 2: %d\n", Search( root, 2 ) );
	printf( "Contains 5: %d\n", Search( root, 5 ) );
	printf( "Contains 6: %d\n", Search( root, 6 ) );

	Free( root );
	root = NULL;
	return 0;
}

/* Output

Contains 9: 1
Contains 2: 0
Contains 9: 1
Contains 2: 0
Contains 5: 0
Contains 6: 1

*/