# Binary search tree (C)

### From LiteratePrograms

**Other implementations**:**C**| C++ | Haskell | Java | Scheme | Standard ML

This article implements a simple binary search tree data structure in C with search, insert, and delete operations. A binary search tree is a tree where each node contains a value, and for each node, the left subtree only contains values less than the value of the node, and the right subtree only contains greater values. This allows to find the node for any value in *O*(log*N*) average time.

The binary search tree shall work with any data type, therefore the code takes pointers to void for the data, and relies on an user-supplied comparison function for sorting.

## Contents |

## Node structure

We begin by defining a node structure, which contains left and right child pointers and a pointer to void referring to the node's data:

<<node structure>>=structbst_node{void* data;structbst_node* left;structbst_node* right;};

We represent an entire tree using a pointer to its root node; thus this structure doubles as a tree representation. Constructing and destroying nodes is straightforward. Newly constructed nodes initially are leaf nodes, i.e. they have no left or right child:

<<declarations>>=structbst_node* new_node(void* data);<<node constructor>>=structbst_node* new_node(void* data){structbst_node* result = malloc(sizeof(structbst_node)); result->data = data; result->left = result->right = NULL;returnresult;}

NULL requires stdlib.h:

<<header files>>=#include <stdlib.h>

On destroying nodes, it is assumed that the node has already been removed from the tree. Especially there are no subtrees to destroy. Moreover, this search tree implementation doesn't take over ownership of the data values, therefore the data pointer doesn't have to be destroyed either.

<<declarations>>=voidfree_node(structbst_node* node);<<node destructor>>=voidfree_node(structbst_node* node){free(node);}

Since our data is generic, the comparison function is supplied by the user via a function pointer and must be the same for all operations. We choose to use a three-way comparator:

<<type definitions>>=/* Returns negative (left<right), zero (left==right), or positive (left>right). */typedefintcomparator(void* left,void* right);

## Search

The most important operation on the tree is searching, which uses the properties of the binary search tree to traverse from the root down towards a given node. In the end it will either find the requested node or prove that it is not in the tree, in which case it returns a pointer to NULL. We return the address of the node pointer instead of just the node pointer to facilitate in-place updates.

<<declarations>>=structbst_node** search(structbst_node** root, comparator compare,void* data);<<search operation>>=structbst_node** search(structbst_node** root, comparator compare,void* data){structbst_node** node = root;while(*node != NULL){intcompare_result = compare(data, (*node)->data);if(compare_result < 0) node = &(*node)->left;elseif(compare_result > 0) node = &(*node)->right;elsebreak;}returnnode;}

## Insert

Inserting is now simple. We search for the node, and if it is not found, we create a new node and put it in the place the search function expected to find it, which is where it belongs in the tree. This particular insertion function does not allow duplicate values in the tree (set semantics), but one that does would be similar.

<<declarations>>=voidinsert(structbst_node** root, comparator compare,void* data);<<insert operation>>=voidinsert(structbst_node** root, comparator compare,void* data){structbst_node** node = search(root, compare, data);if(*node == NULL){*node = new_node(data);}}

## Deletion

Deletion is the most complicated operation. We focus on deleting nodes rather than values, since `search()`

can be used to find a node based on a value if necessary. Deleting a node with one child or less is simple; we just replace it with its child:

<<declarations>>=voiddelete(structbst_node** node);<<delete operation>>=voiddelete(structbst_node** node){structbst_node* old_node = *node;if((*node)->left == NULL){*node = (*node)->right; free_node(old_node);}elseif((*node)->right == NULL){*node = (*node)->left; free_node(old_node);}else{delete node with two children}}

A node's *inorder predecessor* is the node whose value immediately precedes the node's value in sorted order. We can find this node by following right child pointers repeatedly starting at the node's left child. Similarly, the *inorder successor* immediately follows it in sorted order, and can be found by following left child pointers starting at the node's right child.

<<find inorder predecessor>>=structbst_node** pred = &(*node)->left;while((*pred)->right != NULL){pred = &(*pred)->right;}

To delete a node with two children, as shown below, we simply exchange the value of the node with either its inorder predecessor or successor, then delete the node that we exchanged with. This preserves the order properties of the tree, and the predecessor/successor nodes always have at most one child, so we already know how to delete them. In this implementation, we choose to consistently use the predecessor.

<<delete node with two children>>=find inorder predecessor /* Swap values */void* temp = (*pred)->data; (*pred)->data = (*node)->data; (*node)->data = temp; delete(pred);

## Files

We can place this implementation in a source and header file for reuse:

<<bst.h>>=#ifndef _BST_H_type definitions node structure declarations#endif<<bst.c>>=header files#include "bst.h"search operation insert operation delete operation

This completes the implementation.