binary_search_tree.c File Reference

A basic unbalanced binary search tree implementation in C. More...

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

Include dependency graph for binary_search_tree.c:

Data Structures
struct	node
	Node, the basic data structure in the tree. More...

Typedefs
typedef struct node	node
	Node, the basic data structure in the tree.

Functions
node *	newNode (int data)
	The node constructor, which receives the key value input and returns a node pointer. More...
node *	insert (node *root, int data)
	Insertion procedure, which inserts the input key in a new node in the tree. More...
node *	getMax (node *root)
	Utilitary procedure to find the greatest key in the left subtree. More...
node *	delete (node *root, int data)
	Deletion procedure, which searches for the input key in the tree and removes it if present. More...
int	find (node *root, int data)
	Search procedure, which looks for the input key in the tree and returns 1 if it's present or 0 if it's not in the tree. More...
int	height (node *root)
	Utilitary procedure to measure the height of the binary tree. More...
void	purge (node *root)
	Utilitary procedure to free all nodes in a tree. More...
void	inOrder (node *root)
	Traversal procedure to list the current keys in the tree in order of value (from the left to the right) More...
int	main ()
	Main funcion.

Detailed Description

A basic unbalanced binary search tree implementation in C.

The implementation has the following functionalities implemented:

• Insertion
• Deletion
• Search by key value
• Listing of node keys in order of value (from left to right)

Function Documentation

delete()

node* delete	(	node *	root,
		int	data
	)

Deletion procedure, which searches for the input key in the tree and removes it if present.

Parameters

root	pointer to parent node
data	value to search for int the node

Returns

pointer to parent node

{
    // If the root is null, nothing to be done
    if (root == NULL)
    {
        return root;
    }
    else if (data > root->data)
    {  // If the input key is greater than the root's, search in the right
        // subtree
        root->right = delete (root->right, data);
    }
    else if (data < root->data)
    {  // If the input key is lower than the root's, search in the left subtree
        root->left = delete (root->left, data);
    }
    else if (data == root->data)
    {
        // If the input key matches the root's, check the following cases
        // termination condition
        if ((root->left == NULL) && (root->right == NULL))
        {  // Case 1: the root has no leaves, remove the node
            free(root);
            return NULL;
        }
        else if (root->left == NULL)
        {  // Case 2: the root has one leaf, make the leaf the new root and
            // remove
            // the old root
            node *tmp = root;
            root = root->right;
            free(tmp);
            return root;
        }
        else if (root->right == NULL)
        {
            node *tmp = root;
            root = root->left;
            free(tmp);
            return root;
        }
        else
        {  // Case 3: the root has 2 leaves, find the greatest key in the left
            // subtree and switch with the root's
 
            // finds the biggest node in the left branch.
            node *tmp = getMax(root->left);
 
            // sets the data of this node equal to the data of the biggest node
            // (lefts)
            root->data = tmp->data;
            root->left = delete (root->left, tmp->data);
        }
    }
    return root;
}

Here is the call graph for this function:

find()

int find	(	node *	root,
		int	data
	)

Search procedure, which looks for the input key in the tree and returns 1 if it's present or 0 if it's not in the tree.

Parameters

root	pointer to parent node
data	value to store int he new node

Returns

0 if value not found in the nodes

1 if value was found

{
    // If the root is null, the key's not present
    if (root == NULL)
    {
        return 0;
    }
    else if (data > root->data)
    {
        // If the input key is greater than the root's, search in the right
        // subtree
        return find(root->right, data);
    }
    else if (data < root->data)
    {
        // If the input key is lower than the root's, search in the left subtree
        return find(root->left, data);
    }
    else if (data == root->data)
    {
        // If the input and the root key match, return 1
        return 1;
    }
    else
    {  // unknown result!!
        return 0;
    }
}

getMax()

node* getMax

(

node *

root

)

Utilitary procedure to find the greatest key in the left subtree.

Parameters

root	pointer to parent node

Returns

pointer to parent node

{
    // If there's no leaf to the right, then this is the maximum key value
    if (root->right != NULL)
    {
        return getMax(root->right);
    }
    return root;
}

height()

int height

(

node *

root

)

Utilitary procedure to measure the height of the binary tree.

Parameters

root	pointer to parent node
data	value to store int he new node

Returns

0 if value not found in the nodes

height of nodes to get to data from parent node

{
    // If the root is null, this is the bottom of the tree (height 0)
    if (root == NULL)
    {
        return 0;
    }
    else
    {
        // Get the height from both left and right subtrees to check which is
        // the greatest
        int right_h = height(root->right);
        int left_h = height(root->left);
 
        // The final height is the height of the greatest subtree(left or right)
        // plus 1(which is the root's level)
        if (right_h > left_h)
        {
            return (right_h + 1);
        }
        else
        {
            return (left_h + 1);
        }
    }
}

inOrder()

void inOrder

(

node *

root

)

Traversal procedure to list the current keys in the tree in order of value (from the left to the right)

Parameters

root	pointer to parent node

{
    if (root != NULL)
    {
        inOrder(root->left);
        printf("\t[ %d ]\t", root->data);
        inOrder(root->right);
    }
}

insert()

node* insert	(	node *	root,
		int	data
	)

Insertion procedure, which inserts the input key in a new node in the tree.

Parameters

root	pointer to parent node
data	value to store int he new node

Returns

pointer to parent node

{
    // If the root of the subtree is null, insert key here
    if (root == NULL)
    {
        root = newNode(data);
    }
    else if (data > root->data)
    {
        // If it isn't null and the input key is greater than the root key,
        // insert in the right leaf
        root->right = insert(root->right, data);
    }
    else if (data < root->data)
    {  // If it isn't null and the input key is lower than the root key, insert
       // in the left leaf
        root->left = insert(root->left, data);
    }
    // Returns the modified tree
    return root;
}

Here is the call graph for this function:

newNode()

node* newNode

(

int

data

)

The node constructor, which receives the key value input and returns a node pointer.

Parameters

data	data to store in a new node

Returns

new node with the provided data

Note

the node must be deleted before program terminates to avoid memory leaks

{
    // creates a slug
    node *tmp = (node *)malloc(sizeof(node));
 
    // initializes the slug
    tmp->data = data;
    tmp->left = NULL;
    tmp->right = NULL;
 
    return tmp;
}

purge()

void purge

(

node *

root

)

Utilitary procedure to free all nodes in a tree.

Parameters

root	pointer to parent node

{
    if (root != NULL)
    {
        if (root->left != NULL)
        {
            purge(root->left);
        }
        if (root->right != NULL)
        {
            purge(root->right);
        }
        free(root);
        root = NULL;  // reset pointer
    }
}