Tag Archives: Data Structures

Min-Heap in C

This is a binary min-heap using a dynamic array for storage.

Header file:

#ifndef MINHEAP_H
#define MINHEAP_H

#include <dynarray.h>

struct entry
{
    void *item;
    unsigned int value;
};
typedef struct entry entry;

struct minheap
{
    dynarray *entries;
};
typedef struct minheap minheap;

typedef void(*minheap_forfn)(void*);

minheap *minheap_create(void);
void minheap_delete(minheap *heap);
void minheap_add(minheap *heap, void *item, unsigned int value);
void *minheap_remove_min(minheap *heap);
void minheap_for_each(const minheap *heap, minheap_forfn fun);
unsigned int minheap_get_count(const minheap *heap);

#endif /* MINHEAP_H */

Implementation:

#include <stdlib.h>

#include <minheap.h>

static entry *entry_create(void *item, unsigned int value)
{
    entry *e = malloc(sizeof(entry));
    if (e) {
        e->item = item;
        e->value = value;
    }
    return e;
}

minheap *minheap_create(void)
{
    minheap *heap = malloc(sizeof(minheap));
    if (heap) {
        heap->entries = dynarray_create();
    }
    return heap;
}

void minheap_delete(minheap *heap)
{
    if (heap) {
        dynarray_for_each(heap->entries, free);
        dynarray_delete(heap->entries);
        free(heap);
    }
}

static void minheap_swap(minheap *heap, unsigned int index1, unsigned int index2)
{
    void *temp = dynarray_get(heap->entries, index1);
    dynarray_set(heap->entries, index1, dynarray_get(heap->entries, index2));
    dynarray_set(heap->entries, index2, temp);
}

static void minheap_bubble_up(minheap *heap, unsigned int index)
{
    entry *e = dynarray_get(heap->entries, index);
    unsigned int parent_index = (index - 1) / 2;
    entry *parent = dynarray_get(heap->entries, parent_index);
    if (e->value < parent->value) {
        minheap_swap(heap, index, parent_index);
        if (parent_index > 0) {
            minheap_bubble_up(heap, parent_index);
        }
    }
}

static void minheap_bubble_down(minheap *heap, unsigned int index)
{
    entry *e = dynarray_get(heap->entries, index);
    unsigned int left_child_index = (index * 2) + 1;
    unsigned int right_child_index = left_child_index + 1;
    unsigned int swapped = 0;
    unsigned int swapped_index;
    if (right_child_index < dynarray_get_count(heap->entries) /* There is a right child */
            && ((entry*)dynarray_get(heap->entries, right_child_index))->value 
                    < ((entry*)dynarray_get(heap->entries, left_child_index))->value 
                   /* And it's less than left child */
            && e->value > ((entry*)dynarray_get(heap->entries, right_child_index))->value) {
        minheap_swap(heap, index, right_child_index);
        swapped = 1;
        swapped_index = right_child_index;
    }
    else if (e->value > ((entry*)dynarray_get(heap->entries, left_child_index))->value) {
        minheap_swap(heap, index, left_child_index);
        swapped = 1;
        swapped_index = left_child_index;
    }
    if (swapped && (swapped_index * 2) + 1 < dynarray_get_count(heap->entries) - 1) {
        minheap_bubble_down(heap, swapped_index);
    }
}

void minheap_add(minheap *heap, void *item, unsigned int value)
{
    entry *e = entry_create(item, value);
    if (e) {
        dynarray_add_tail(heap->entries, e);
        unsigned int count = dynarray_get_count(heap->entries);
        if (count > 1) {
            minheap_bubble_up(heap, count - 1);
        }
    }
}

void *minheap_remove_min(minheap *heap)
{
    void *item = NULL;
    unsigned int count = dynarray_get_count(heap->entries);
    if (count > 1) {
        minheap_swap(heap, 0, count - 1);
    }
    if (count > 0) {
        entry *e = dynarray_remove_tail(heap->entries);
        item = e->item;
        free(e);
    }
    if (dynarray_get_count(heap->entries) > 1) {
        minheap_bubble_down(heap, 0);
    }
    return item;
}

void minheap_for_each(const minheap *heap, minheap_forfn fun)
{
    dynarray_for_each(heap->entries, (dynarray_forfn)fun);
}

unsigned int minheap_get_count(const minheap *heap)
{
    return dynarray_get_count(heap->entries);
}

Example program:

#include <stdio.h>

#include <minheap.h>

int main(void)
{
    minheap *heap = minheap_create();
    unsigned int numbers[10];
    unsigned int i;
    for (i = 0; i < 10; i++) {
        numbers[i] = i;
        minheap_add(heap, &(numbers[i]), i);
    }
    printf("Count is %u\n", minheap_get_count(heap));
    for (i = 0; i < 10; i++) {
        const int *e = minheap_remove_min(heap);
        if (e) {
            printf("%d\n", *e);
        }
    }
    printf("Count is now %u\n", minheap_get_count(heap));
    minheap_delete(heap);
    return 0;
}

Output:

Count is 10
0
1
2
3
4
5
6
7
8
9
Count is now 0

Bulk loading a binary tree with sorted data

If you add sorted data to a binary tree using the conventional binary tree insertion algorithm, the tree will end up as a single rightward-leaning vine, and will perform no better than a sorted linked list.

In order to load sorted data and keep the tree perfectly balanced, it is necessary to add the data in the order in which a binary search would visit it. In other words, the middle element first, then the middle of the left sub-array, the middle of the right sub-array and so on.

Here is an implementation of that algorithm in C:

static void binarytree_load_recursive(btnode ** node, void ** list, size_t size)
{
	if (size > 0) {
		unsigned int left, right, middle = size / 2;
		*node = btnode_create(list[middle]);
		left = middle;
		right = size - middle - 1;
		binarytree_load_recursive(&((*node)->left), list, left);
		binarytree_load_recursive(&((*node)->right), &list[middle + 1], right);
	}
}

void binarytree_load(binarytree * tree, void ** list, size_t size)
{
    binarytree_load_recursive(&(tree->root), list, size);
    tree->count = size;
}

As an example, I load a binary tree from a sorted array and then check its height with the algorithm I described in Finding the Height of a Binary Tree Recursively. The height is 2, which is the optimum height for a tree with 7 nodes.

int main(void)
{
	char *elements[] = {"A", "B", "C", "D","E","F", "G"};
	const unsigned int n = sizeof(elements) / sizeof(const char*);
	binarytree *tree;

	tree = binarytree_create((cmpfn)strcmp);
	binarytree_load(tree, (void*)elements, n);
    printf("Height is %u\n", binarytree_height(tree));
	binarytree_for_each(tree, (forfn)puts);
	binarytree_delete(tree);

	return 0;
}

Output:

Height is 2
A
B
C
D
E
F
G

Here is the rest of the binary tree code:

struct btnode {
	struct btnode * left;
	struct btnode * right;
	void * data;
};
typedef struct btnode btnode;

typedef int(*cmpfn)(const void *, const void *);

struct binarytree {
	btnode * root;
	cmpfn compare;
	unsigned int count;
};
typedef struct binarytree binarytree;

static btnode * btnode_create(void * data)
{
	btnode * node = malloc(sizeof(btnode));
	if (node) {
		node->left = NULL;
		node->right = NULL;
		node->data = data;
	}
	return node;
}

binarytree * binarytree_create(cmpfn compare)
{
	binarytree * tree = malloc(sizeof(binarytree));
	if (tree != NULL) {
		tree->root = NULL;
		tree->compare = compare;
		tree->count = 0;
	}
	return tree;
}

static void binarytree_clear_recursive(btnode * root)
{
	if (root != NULL) {
		btnode * left = root->left;
		btnode * right = root->right;
		free(root);
		binarytree_clear_recursive(left);
		binarytree_clear_recursive(right);
	}
}

void binarytree_clear(binarytree * tree)
{
	binarytree_clear_recursive(tree->root);
	tree->root = NULL;
	tree->count = 0;
}

void binarytree_delete(binarytree * tree)
{
	if (tree) {
		binarytree_clear(tree);
		free(tree);
	}
}

typedef void(*forfn)(const void *);

static void binarytree_for_each_recursive(const btnode * root, forfn fun)
{
	if (root) {
		binarytree_for_each_recursive(root->left, fun);
		fun(root->data);
		binarytree_for_each_recursive(root->right, fun);
	}
}

void binarytree_for_each(const binarytree * tree, forfn fun)
{
	binarytree_for_each_recursive(tree->root, fun);
}

static void binarytree_load_recursive(btnode ** node, void ** list, size_t size)
{
	if (size > 0) {
		unsigned int left, right, middle = size / 2;
		*node = btnode_create(list[middle]);
		left = middle;
		right = size - middle - 1;
		binarytree_load_recursive(&((*node)->left), list, left);
		binarytree_load_recursive(&((*node)->right), &list[middle + 1], right);
	}
}

void binarytree_load(binarytree * tree, void ** list, size_t size)
{
    binarytree_load_recursive(&(tree->root), list, size);
    tree->count = size;
}

static int max(int a, int b)
{
    if (a >= b) {
        return a;
    }
    return b;
}
 
unsigned int binarytree_height_recursive(const btnode *node)
{
    unsigned int height = 0;
    if (node->left || node->right) {
        height = max(node->left ? binarytree_height_recursive(node->left) : 0,
                node->right ? binarytree_height_recursive(node->right) : 0) + 1;
    }
    return height;
}
 
unsigned int binarytree_height(const binarytree *tree)
{
    unsigned int height = 0;
    if (tree->root) {
        height = binarytree_height_recursive(tree->root);
    }
    return height;
}

BK-Tree in C++

A BK-tree is an efficient data structure for storing items for which there is some concept of distance between them. A common use is to store words for approximate string matching, using the Levenshtein distance metric. Another use is to store phrases using some measure of semantic distance in order to implement an AI system like a chatterbot.

This is a simple implementation of a BK-tree in C++.

#ifndef BK_TREE_HPP
#define BK_TREE_HPP

#include <map>
#include <memory>
#include <type_traits>

namespace MB
{

template <typename T, typename Unit, typename Metric> class bktree;

namespace detail
{

template <typename T, typename Unit, typename Metric>
class bktree_node
{
    friend class bktree<T, Unit, Metric>;
	typedef bktree_node<T, Unit, Metric> node_type;
    typedef std::unique_ptr<node_type> node_ptr_type;
	
	T value_;
	std::map<Unit, node_ptr_type> children_;

	bktree_node(const T &value)
		: value_(value)
    {
    }

	bool insert(const T& value, const Metric& distance)
    {
        bool inserted = false;
		Unit dist = distance(value, this->value_);
		if (dist > 0) {
            // Not already here 
            auto it = children_.find(dist);
            if (it == children_.end()) {
                // Attach a new edge here
                children_.insert(std::make_pair(dist, node_ptr_type(new node_type(value))));
                inserted = true;
            }
            else {
                // Follow existing edge
                inserted = it->second->insert(value, distance);
            }
            return inserted;
        }
	}

    template <class OutputIt>
	OutputIt find(const T &value, const Unit& limit, const Metric& distance, OutputIt it) const
    {
		Unit dist = distance(value, this->value_);
		if (dist <= limit) {
            // Found one
			*it++ = std::make_pair(this->value_, dist);
        }
		for (auto iter = children_.begin(); iter != children_.end(); ++iter) {
            // Follow edges between dist + limit and dist - limit
			if (dist - limit <= iter->first && dist + limit >= iter->first) {
				iter->second->find(value, limit, distance, it);
            }
		}
        return it;
	}
};

}; // namespace detail

template <typename T, typename Unit, typename Metric>
class bktree
{
private:
	typedef typename detail::bktree_node<T, Unit, Metric>::node_type node_type;
    typedef typename detail::bktree_node<T, Unit, Metric>::node_ptr_type node_ptr_type;

    node_ptr_type head_;
    const Metric distance_;
	size_t size_;

public:
	bktree(const Metric& distance = Metric())
        : head_(nullptr), distance_(distance), size_(0L)
    {
        static_assert(std::is_integral<Unit>::value, "Integral unit type required.");
    }

	bool insert(const T &value)
    {
        bool inserted = false;
		if (head_ == nullptr) {
            // Inserting the first value
			head_ = node_ptr_type(new node_type(value));
			size_ = 1;
            inserted = true;
		}
        else if (head_->insert(value, distance_)) {
            ++size_;
            inserted = true;
        }
        return inserted;
	}

    template <class OutputIt>
	OutputIt find(const T& value, const Unit& limit, OutputIt it) const
    {
		return head_->find(value, limit, distance_, it);
	}

	size_t size() const
    {
		return size_;
	}
};

}; // namespace MB

#endif // BK_TREE_HPP

Here is an example program. It loads a dictionary from a file, and then prompts the user to enter words and a limit on distance, and it will return all words within that Levenshtein distance of the word entered. I used this dictionary with it:

#include <fstream>
#include <iostream>
#include <string>

#include "bk_tree.hpp"
#include "levenshtein_distance.hpp"

int main()
{
    const char filename[] = "dictionary.txt";
    std::ifstream ifs(filename);
    if (!ifs) {
        std::cerr << "Couldn't open " << filename << " for reading\n";
        return 1;
    }
    MB::bktree<std::string, int, levenshtein_distance> tree;
    std::string word;
    while (ifs >> word) {
        tree.insert(word);
    }
    std::cout << "Inserted " << tree.size() << " words\n";
    std::vector<std::pair<std::string, int> > results;
    do {
        std::cout << "Enter a word (\"quit!\" to quit)> ";
        std::cin >> word;
        if (word != "quit!") {
            int limit;
            std::cout << "Enter a limit> ";
            std::cin >> limit;
            tree.find(word, limit, std::back_inserter(results));
            for (auto it = results.begin(); it != results.end(); ++it) {
                std::cout << it->first << "(distance " << it->second << ")\n";
            }
            results.clear();
        }
    }  while (word != "quit!");
}

Example run:

$ ./dictionary
Inserted 127142 words
Enter a word ("quit!" to quit)> mispelling
Enter a limit> 2
spelling(distance 2)
misdealing(distance 2)
impelling(distance 2)
miscalling(distance 2)
mispenning(distance 2)
misrelying(distance 2)
respelling(distance 2)
dispelling(distance 1)
misbilling(distance 2)
misspelling(distance 1)
misspellings(distance 2)
Enter a word ("quit!" to quit)> quit!
$

Here is an implementation of the Levenshtein distance:

#include <string>
#include <vector>
#include <algorithm>

namespace MB
{

namespace detail
{

template <typename T>
T min3(const T& a, const T& b, const T& c)
{
   return std::min(std::min(a, b), c);
}

}; // namespace detail

class levenshtein_distance 
{
    mutable std::vector<std::vector<unsigned int> > matrix_;

public:
    explicit levenshtein_distance(size_t initial_size = 8)
        : matrix_(initial_size, std::vector<unsigned int>(initial_size))
    {
    }

    unsigned int operator()(const std::string& s, const std::string& t) const
    {
        const size_t m = s.size();
        const size_t n = t.size();
        // The distance between a string and the empty string is the string's length
        if (m == 0) {
            return n;
        }
        if (n == 0) {
            return m;
        }
        // Size the matrix as necessary
        if (matrix_.size() < m + 1) {
            matrix_.resize(m + 1, matrix_[0]);
        }
        if (matrix_[0].size() < n + 1) {
            for (auto& mat : matrix_) {
                mat.resize(n + 1);
            }
        }
        // The top row and left column are prefixes that can be reached by
        // insertions and deletions alone
        unsigned int i, j;
        for (i = 1;  i <= m; ++i) {
            matrix_[i][0] = i;
        }
        for (j = 1; j <= n; ++j) {
            matrix_[0][j] = j;
        }
        // Fill in the rest of the matrix
        for (j = 1; j <= n; ++j) {
            for (i = 1; i <= m; ++i) {
                unsigned int substitution_cost = s[i - 1] == t[j - 1] ? 0 : 1;
                matrix_[i][j] =
                    detail::min3(matrix_[i - 1][j] + 1,         // Deletion
                    matrix_[i][j - 1] + 1,                      // Insertion
                    matrix_[i - 1][j - 1] + substitution_cost); // Substitution
            }
        }
        return matrix_[m][n];
    }
};

}; // namespace MB

AVL Tree in C

An AVL tree is a height-balanced binary search tree in which the heights of a node’s two sub-trees are not allowed to differ by more than one.
For example, the first tree below is balanced, while the other two are unbalanced because they are "heavy" on one side or the other:

                   A                          C
                    \                        /
      B              B                      B
     / \               \                   /
    A   C               C                 A
                          
   Balanced      Not Balanced          Not Balanced        
                 "Right Heavy"         "Left Heavy"         

If a tree becomes unbalanced by an addition or deletion, the balance can be restored by rotations, which change the shape of the tree, but preserve the BST property. Below are a left rotation at A, and a right rotation at C:

        A                                    C
         \                                  /
           B      -->      B               B      -->      B
            \             / \            /                / \
             C           A   C          A                A   C     

            Left Rotation                     Right Rotation          

Some unbalanced trees cannot be balanced by a single rotation.
For example, the two trees below are simply converted into each other by a single rotation of the top node:

   C         -->        A     
  /      Rotate Right    \
 B                        C
  \         <--          /
    A    Rotate Left    B

In this case we need to do a double rotation:

  • A double left rotation is a left rotation on the left subtree followed by a right rotation on the root
  • A double right rotation is a right rotation on the right subtree followed by a left rotation on the root

For example, here is a double left rotation:

   C               C            
  /               /
 A      -->      B      -->      B      
  \             /               / \
   B           A               A   C

1. Rotate Left at A   2. Rotate Right at C

Here is the header file:

#ifndef AVLTREE_H
#define AVLTREE_H

#include <stdlib.h>

struct avltreenode
{
	struct avltreenode * left;
	struct avltreenode * right;
	struct avltreenode * parent;
	unsigned int leftheight;
	unsigned int rightheight;
	void * data;
};

typedef struct avltreenode avltreenode;

typedef int (*avltree_cmpfn)(const void*, const void*);
typedef void (*avltree_forfn)(void*);

struct avltree {
	avltreenode * root;
	size_t count;
	avltree_cmpfn compare;
};

typedef struct avltree avltree;

avltree * avltree_create(avltree_cmpfn compare);
void avltree_delete(avltree * tree);
void avltree_for_each(const avltree * tree, avltree_forfn fun);
void* avltree_add(avltree * tree, void * data);
void* avltree_find(const avltree * tree, const void* data);
void* avltree_remove(avltree * tree, const void* data);
void avltree_empty(avltree * tree);
size_t avltree_get_count(const avltree *tree);

#endif /* AVLTREE_H */

The implementation:

#include <stdlib.h>

#include <avltree.h>

avltree * avltree_create(avltree_cmpfn compare)
{
	avltree * tree = malloc(sizeof(avltree));
	if (tree != NULL) {
		tree->root = NULL;
		tree->compare = compare;
		tree->count = 0;
	}
	return tree;
}

static void avltreenode_delete(avltreenode *node)
{
	free(node);
}

static void avltree_empty_recursive(avltreenode * root)
{
	if (root->left) {
		avltree_empty_recursive(root->left);
	}
	if (root->right) {
		avltree_empty_recursive(root->right);
	}
	avltreenode_delete(root);
}

void avltree_empty(avltree * tree)
{
    if (tree->root) {
        avltree_empty_recursive(tree->root);
        tree->root = NULL;
        tree->count = 0;
    }
}

void avltree_delete(avltree * tree)
{
	if (tree) {
		avltree_empty(tree);
		free(tree);
	}
}

static void avltree_for_each_recursive(const avltreenode * root, avltree_forfn fun)
{
	if (root->left != NULL) {
		avltree_for_each_recursive(root->left, fun);
	}
	fun(root->data);
	if (root->right != NULL) {
		avltree_for_each_recursive(root->right, fun);
	}
}

void avltree_for_each(const avltree * tree, avltree_forfn fun)
{
    if (tree->root) {
        avltree_for_each_recursive(tree->root, fun);
    }
}

struct avlsearchresult
{
	avltreenode *node;
	avltreenode *parent;
};
typedef struct avlsearchresult avlsearchresult;

static int avltree_search(const avltree *tree, avlsearchresult *result, const void *data)
{
	int found = 0;

	result->node = tree->root;
	while (!found && result->node != NULL) {
		int rv = tree->compare(result->node->data, data);
		if (rv == 0) {
			found = 1;
		}
		else {
			result->parent = result->node;
			if (rv > 0) {
				result->node = result->node->left;
			}
			else if (rv < 0) {
				result->node = result->node->right;
			}
		}
	}
	return found;
}

static avltreenode * avltreenode_create(void * data)
{
	avltreenode * node = malloc(sizeof(avltreenode));
	if (node) {
		node->left = NULL;
		node->right = NULL;
		node->parent = NULL;
		node->leftheight = 0;
		node->rightheight = 0;
		node->data = data;
	}
	return node;
}

static int avltreenode_get_max_height(const avltreenode *node)
{
	int height;
	if (node->leftheight > node->rightheight) {
		height = node->leftheight;
	}
	else {
		height = node->rightheight;
	}
	return height;
}

static void avltreenode_fix_height(avltreenode *node)
{
	node->leftheight = 0;
	node->rightheight = 0;
	if (node->left) {
		node->leftheight = avltreenode_get_max_height(node->left) + 1;
	}
	if (node->right) {
		node->rightheight = avltreenode_get_max_height(node->right) + 1;
	}
}

static void avltree_rotate_left(avltree *tree, avltreenode *node)
{
	avltreenode *right = node->right;
	if (node == tree->root) {
		tree->root = right;
	}
	else if (node == node->parent->left) {
		node->parent->left = right;
	}
	else {
		node->parent->right = right;
	}
    right->parent = node->parent;
	if (right->left) {
		node->right = right->left;
        node->right->parent = node;
	}
	else {
		node->right = NULL;
	}
	right->left = node;
    node->parent = right;
	avltreenode_fix_height(node);
	avltreenode_fix_height(right);
}

static void avltree_rotate_right(avltree *tree, avltreenode *node)
{
	avltreenode *left = node->left;
	if (node == tree->root) {
		tree->root = left;
	}
	else if (node == node->parent->left) {
		node->parent->left = left;
	}
	else {
		node->parent->right = left;
	}
    left->parent = node->parent;
	if (left->right) {
		node->left = left->right;
        node->left->parent = node;
	}
	else {
		node->left = NULL;
	}
	left->right = node;
    node->parent = left;
	avltreenode_fix_height(node);
	avltreenode_fix_height(left);
}

static int avltreenode_get_balance_factor(const avltreenode *node)
{
	return node->leftheight - node->rightheight;
}

static void avltree_rebalance(avltree *tree, avltreenode *node)
{
	avltreenode *current = node;
	while (current != NULL) {
        avltreenode *parent = current->parent;
		int balance;
		avltreenode_fix_height(current);
		balance = avltreenode_get_balance_factor(current);
		if (balance == -2) {
			/* Right heavy */
			const int rightbalance = avltreenode_get_balance_factor(current->right);
			if (rightbalance < 0) {
				avltree_rotate_left(tree, current);
			}
			else {
				avltree_rotate_right(tree, current->right);
				avltree_rotate_left(tree, current);
			}
		}
		else if (balance == 2) {
			/* Left heavy */
			const int leftbalance = avltreenode_get_balance_factor(current->left);
			if (leftbalance > 0) {
				avltree_rotate_right(tree, current);
			}
			else {
				avltree_rotate_left(tree, current->left);
				avltree_rotate_right(tree, current);
			}
		}
        current = parent;
	}
}

void* avltree_add(avltree * tree, void * data)
{
	void *temp = NULL;
	avlsearchresult result;
	result.node = NULL;
	result.parent = NULL;

	if (avltree_search(tree, &result, data)) {
		temp = result.node->data;
		result.node->data = data;
	}
	else {
		avltreenode *node = avltreenode_create(data);
		if (result.node == tree->root) {
			tree->root = node;
		}
		else {
			int rv = tree->compare(data, result.parent->data);
			if (rv < 0) {
				result.parent->left = node;
			}
			else {
				result.parent->right = node;
			}
			node->parent = result.parent;
            avltree_rebalance(tree, node);
		}
		tree->count++;
	}
	
	return temp;
}

void* avltree_find(const avltree * tree, const void* data)
{
	void *temp = NULL;
	avlsearchresult result;
	result.node = NULL;
	result.parent = NULL;

	if (avltree_search(tree, &result, data)) {
		temp = result.node->data;
	}
	return temp;
}

static avltreenode *avltreenode_find_min(avltreenode *node)
{
	avltreenode *current = node;

	while (current->left) {
		current = current->left;
	}
	return current;
}

static void avltree_remove_node(avltree *tree, avltreenode *node)
{
	if (node->left && node->right) {
        /* Node with 2 children */
		avltreenode *successor = avltreenode_find_min(node->right);
		node->data = successor->data;
		avltree_remove_node(tree, successor);
	}
	else {
        avltreenode *parent = node->parent;
		if (node->left) {
            /* Node with only left child */
			if (node->parent) {
                if (node == node->parent->left) {
				    node->parent->left = node->left;
				    node->parent->left->parent = node->parent;
                }
                else {
				    node->parent->right = node->left;
				    node->parent->right->parent = node->parent;
                }
			}
			else {
				tree->root = node->left;
				tree->root->parent = NULL;
			}
		}
		else if (node->right) {
            /* Node with only right child */
			if (node->parent) {
                if (node == node->parent->left) {
                    node->parent->left = node->right;
                    node->parent->left->parent = node->parent;
                }
                else {
                    node->parent->right = node->right;
                    node->parent->right->parent = node->parent;
                }
			}
			else {
				tree->root = node->right;
				tree->root->parent = NULL;
			}
		}
		else {
            /* Node with no children */
			if (node->parent) {
				if (node == node->parent->left) {
					node->parent->left = NULL;
				}
				else {
					node->parent->right = NULL;
				}
			}
			else {
				tree->root = NULL;
			}
		}
		avltreenode_delete(node);
        avltree_rebalance(tree, parent);
		tree->count--;
	}
}

void* avltree_remove(avltree * tree, const void* data)
{
	void *temp = NULL;
	avlsearchresult result;
	result.node = NULL;
	result.parent = NULL;

	if (avltree_search(tree, &result, data)) {
		temp = result.node->data;
		avltree_remove_node(tree, result.node);
	}
	return temp;
}

size_t avltree_get_count(const avltree *tree)
{
    return tree->count;
}

Here is an example program:

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

#include <avltree.h>

int main(void)
{
    avltree * tree;
    const char * result;
    unsigned int e;
    char * elements[] = {"orange", "apple", "pear", "grapefruit", "cherry", "plum"};
    const unsigned int n = sizeof(elements) / sizeof(const char*);

    tree = avltree_create((avltree_cmpfn)strcmp);
    for (e = 0; e < n; e++) {
        avltree_add(tree, elements[e]);
    }
    avltree_for_each(tree, (avltree_forfn)puts);
    for (e = 0; e < n; e++) {
        result = avltree_find(tree, elements[e]);
        if (result) {
            printf("Found: %s\n", result); 
        }
        else {
            printf("Couldn't find %s\n", elements[e]);
        }
    }
    for (e = 0; e < n; e++) {
        result = avltree_remove(tree, elements[e]);
        if (result) {
            printf("Removed: %s\n", result);
        }
        else {
            printf("Couldn't remove %s\n", elements[e]);
        }
    }
    avltree_delete(tree);

    return 0;
}

Cirque in C

A circular queue, or cirque, or ring buffer is an array that wraps around, so that it can be used as a queue without walking backwards in memory.

This implementation reallocates the buffer when it becomes full (i.e., when the head and tail of the queue meet).

The header file:

#ifndef CIRQUE_H
#define CIRQUE_H

struct cirque {
	unsigned int head; /* First element */
	unsigned int tail; /* 1 past the last element */
	unsigned int is_full;
	void ** entries;
	unsigned int size;
};
typedef struct cirque cirque;

typedef void (*cirque_forfn)(void*);

cirque * cirque_create(void);
void cirque_delete(cirque * queue);
unsigned int cirque_insert(cirque * queue, void * data);
void *  cirque_remove(cirque * queue);
void *cirque_peek(const cirque * queue);
unsigned int cirque_get_count(const cirque * queue);
void cirque_for_each(const cirque * queue, cirque_forfn fun);

#endif /* CIRQUE_H */

Implementation:

#include <stdlib.h>

#include <cirque.h>

cirque * cirque_create(void)
{
    const unsigned int size = 4;
	cirque * queue = malloc(sizeof(cirque));
	if (queue) {
		queue->entries = malloc(size * sizeof(void *));
		if (queue->entries) {
			queue->size = size;
			queue->head = 0;
			queue->tail = 0;
			queue->is_full = 0;
		}
		else {
			free(queue);
			queue = NULL;
		}
	}
	return queue;
}

void cirque_delete(cirque * queue)
{
	if (queue) {
		free(queue->entries);
		free(queue);
	}
}

static void cirque_resize(cirque * queue)
{
	void **temp = malloc(queue->size * 2 * sizeof(void *));
	if (temp) {
		unsigned int i = 0;
		unsigned int h = queue->head;
		do {
			temp[i] = queue->entries[h++];
			if (h == queue->size) {
				h = 0;
			}
			i++;
		} while (h != queue->tail);
		free(queue->entries);
		queue->entries = temp;
		queue->head = 0;
		queue->tail = queue->size;
		queue->size *= 2;
		queue->is_full = 0;
	}
}

static unsigned int cirque_is_empty(const cirque * queue)
{
	return (queue->head == queue->tail) && !queue->is_full;
}

unsigned int cirque_insert(cirque * queue, void * data)
{
	unsigned int result;
	if (queue->is_full) {
		cirque_resize(queue);
		if (queue->is_full) {
			result = 0;
		}
	}
	if (!queue->is_full) {
		queue->entries[queue->tail++] = data;
		if (queue->tail == queue->size) {
			queue->tail = 0;
		}
		if (queue->tail == queue->head) {
			queue->is_full = 1;
		}
		result = 1;
	}
	return result;
}

void * cirque_remove(cirque * queue)
{
	void * data = NULL;
	if (!cirque_is_empty(queue)) {
		if (queue->is_full) {
			queue->is_full = 0;
		} 
		data = queue->entries[queue->head++];
		if (queue->head == queue->size) {
			queue->head = 0;
		}
	}
	return data;
}
  
void *cirque_peek(const cirque * queue)
{
	void *data = NULL;
	if (!cirque_is_empty(queue)) {
		data = queue->entries[queue->head];
	}
	return data;
}

unsigned int cirque_get_count(const cirque * queue)
{
	unsigned int count;
   	if (cirque_is_empty(queue)) {
		count = 0;
	}
	else if (queue->is_full) {
		count = queue->size;
	}
	else if (queue->tail > queue->head) {
		count = queue->tail - queue->head;
	}
	else {
		count = queue->size - queue->head;
		if (queue->tail > 0) {
			count += queue->tail - 1;
		}
	}
	return count;
}

void cirque_for_each(const cirque * queue, cirque_forfn fun)
{
	if (!cirque_is_empty(queue)) {
		unsigned int h = queue->head;
		do {
			fun(queue->entries[h++]);
			if (h == queue->size) {
				h = 0;
			}
		} while (h != queue->tail);
	}
}

An example program:

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

#include <cirque.h>

int main(void)
{
    cirque * queue;
    char buf[16];
    unsigned int f;
    const unsigned int max = 32;
    const unsigned int limit = 16;

    queue = cirque_create();
    for (f = 0; f < max; f++) {
        sprintf(buf, "Item %d", f);
        if (f >= limit) {
            /* Start removing at limit to show the queue doesn't keep growing */
            char *data = cirque_remove(queue);
            printf("Removed %s\n", data);
            free(data);
        }
        printf("Inserting %s\n", buf);
        cirque_insert(queue, strdup(buf));
    }
    cirque_for_each(queue, (cirque_forfn)puts);
    printf("Size is %d (should be %d)\n", queue->size, limit);
    cirque_for_each(queue, free);
    cirque_delete(queue);

    return 0;
}

Sorted array in C

This is a sorted dynamic array. It allows finding elements in O(log n) time, the same as for a binary search tree. Inserting or deleting elements is in amortized O(n) time because of the need to shift elements to make room or fill gaps.

The main advantages of a sorted array over a binary search tree are:

  • Simpler implementation
  • Better locality of reference, so improved cache performance
  • Iteration does not involve following pointers, just increasing an index variable
  • Finding the nth element is O(1), while it is O(n) in a binary search tree
  • The array, or a range from it, can be copied to another memory location easily without iteration

Here is the header file:

#ifndef SORTEDARRAY_H
#define SORTEDARRAY_H

#include <dynarray.h>

typedef int (*sortedarray_cmpfn)(const void*, const void*);
typedef void (*sortedarray_forfn)(void*);

struct sortedarray {
	dynarray *array;
	sortedarray_cmpfn compare;
};

typedef struct sortedarray sortedarray;

sortedarray * sortedarray_create(sortedarray_cmpfn compare);
void sortedarray_delete(sortedarray * array);
void * sortedarray_add(sortedarray * array, void * data);
void * sortedarray_remove(sortedarray * array, const void * data);
void * sortedarray_find(const sortedarray * array, const void * data);
void sortedarray_for_each(const sortedarray * array, sortedarray_forfn forfn);
unsigned int sortedarray_get_count(const sortedarray *array);
void * sortedarray_get(const sortedarray *array, unsigned int pos);
void * sortedarray_remove_at(sortedarray *array, unsigned int pos);
int sortedarray_find_index(const sortedarray *array, const void *data);

#endif /* SORTEDARRAY_H */

The implementation:

#include <stdlib.h>

#include <sortedarray.h>

sortedarray * sortedarray_create(sortedarray_cmpfn compare)
{
	sortedarray *array = malloc(sizeof(sortedarray));
	if (array) {
		array->array = dynarray_create(0);
		array->compare = compare;
	}
	return array;
}

void sortedarray_delete(sortedarray * array)
{
	if (array) {
		dynarray_delete(array->array);
		free(array);
	}
}

typedef struct {
	void * data;
	unsigned int pos;
} search_result;

static search_result sortedarray_search(const sortedarray *array, const void *data)
{
	search_result sr;
	unsigned int elements = array->array->count;
	unsigned int offset = 0;
	unsigned int middle = 0;
	
	sr.data = NULL;
	while (elements > 0 && !sr.data) {
		int result;
		middle = elements / 2;
		result = array->compare(data, dynarray_get(array->array, offset + middle));
		if (result > 0) {
			offset = offset + middle + 1;
			elements = elements - (middle + 1);
		}
		else if (result < 0) {
			elements = middle;
		}
		else {
			sr.data = dynarray_get(array->array, offset + middle);
			offset += middle;
		}
	}
	sr.pos = offset;

	return sr;
}

void * sortedarray_add(sortedarray * array, void * data)
{
	search_result result = sortedarray_search(array, data);
	void *existing = result.data;
	if (existing) {
		/* Replace */
		dynarray_set(array->array, result.pos, data);
	}
	else {
		/* Add new */
		dynarray_insert(array->array, result.pos, data);
	}
	return existing;
}

void * sortedarray_remove(sortedarray * array, const void * data)
{
	search_result result = sortedarray_search(array, data);
	if (result.data) {
		dynarray_remove(array->array, result.pos);
	}
	return result.data;
}

void * sortedarray_find(const sortedarray * array, const void * data)
{
	search_result result = sortedarray_search(array, data);
	return result.data;
}

void sortedarray_for_each(const sortedarray * array, sortedarray_forfn forfn)
{
	dynarray_for_each(array->array, forfn);
}

unsigned int sortedarray_get_count(const sortedarray *array)
{
	return array->array->count;
}

void * sortedarray_get(const sortedarray *array, unsigned int pos)
{
	return dynarray_get(array->array, pos);
}

void * sortedarray_remove_at(sortedarray * array, unsigned int pos)
{
	return dynarray_remove(array->array, pos);
}

int sortedarray_find_index(const sortedarray *array, const void *data)
{
	int index = -1;
	search_result result = sortedarray_search(array, data);
	if (result.data) {
		index = result.pos;
	}
	return index;
}

An example program:

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

#include <sortedarray.h>

int main(void)
{
    sortedarray * array;
    const char * result;
    unsigned int e;
    char * elements[] = {"orange", "apple", "pear", "grapefruit", "cherry", "plum"};
    const unsigned int n = sizeof(elements) / sizeof(const char*);

    array = sortedarray_create((sortedarray_cmpfn)strcmp);
    for (e = 0; e < n; e++) {
        sortedarray_add(array, elements[e]);
    }
    sortedarray_for_each(array, (sortedarray_forfn)puts);
    for (e = 0; e < n; e++) {
        result = sortedarray_find(array, elements[e]);
        if (result) {
            printf("Found: %s at %d\n", result, 
                    sortedarray_find_index(array, elements[e]));
        }
        else {
            printf("Couldn't find %s\n", elements[e]);
        }
    }
    for (e = 0; e < n; e++) {
        result = sortedarray_remove(array, elements[e]);
        if (result) {
            printf("Removed: %s\n", result);
        }
        else {
            printf("Couldn't remove %s\n", elements[e]);
        }
    }
    sortedarray_delete(array);

    return 0;
}

Singly-linked list in C

A singly-linked list is a simple data structure in which each node has a pointer to the next node in the list. The main difference with a doubly-linked list is that to insert before a node, or remove a node, you need to have found the previous node as well, so that you can change its next pointer. This means that when iterating over the list to perform these modifications you need to keep track of a previous node shadowing the current one as follows:

snode *current, *previous = NULL;
for (current = list->head; current != NULL; current = current->next) {
    /* Modify current, using previous where necessary */
    previous = current;
}

Here is the header file:

#ifndef SLIST_H
#define SLIST_H

struct snode {
	void * data;
	struct snode * next;
};
typedef struct snode snode;

struct slist {
	snode * head;
	snode * tail;
	unsigned int count;
};
typedef struct slist slist;

typedef void (*slist_forfn)(void *);

slist * slist_create(void);
void slist_empty(slist * list);
void slist_delete(slist * list);
void slist_add_tail(slist * list, void * data);
void slist_add_head(slist * list, void * data);
void * slist_remove_head(slist * list);
void * slist_remove_tail(slist * list);
void * slist_remove(slist *list, snode *node, snode *previous);
void slist_insert_before(slist * list, snode * node, snode * previous, void * data);
snode * slist_insert_after(slist * list, snode * node, void * data);
void slist_for_each(const slist * list, slist_forfn fun);
unsigned int slist_get_count(const slist * list);

#endif /* SLIST_H */

The implemention:

#include <stdlib.h>

#include <slist.h>

static snode * snode_create(void * data)
{
	snode * node = malloc(sizeof(snode));
	if (node) {
		node->data = data;
		node->next = NULL;
	}

	return node;
}

slist * slist_create(void)
{
	slist * list = malloc(sizeof(slist));
	if (list) {
		list->head = NULL;
		list->tail = NULL;
		list->count = 0;
	}

	return list;
}

void slist_empty(slist * list)
{
	snode * node, * temp;
	node = list->head;
	while (node != NULL) {
		temp = node->next;
		free(node);
		node = temp;
	}
}

void slist_delete(slist * list)
{
	if (list) {
		slist_empty(list);
		free(list);
	}
}

void slist_add_tail(slist * list, void * data)
{
	snode * node = snode_create(data);
	if (list->head == NULL) {
		/* Adding the first node */
		list->head = node;
		list->tail = node;
	}
	else {
		list->tail->next = node;
		list->tail = node;
	}
	list->count++;
}

void slist_add_head(slist * list, void * data)
{
	snode * node = snode_create(data);
	if (list->tail == NULL) {
		/* Adding the first node */
		list->head = node;
		list->tail = node;
	}
	else {
		node->next = list->head;
		list->head = node;
	}
	list->count++;
}

void * slist_remove_head(slist * list)
{
	void *data = NULL;

	if (list->head) {
		snode *temp = list->head;
		if (list->head->next) {
			list->head = list->head->next;
		}
		else {
			/* List is now empty */
			list->head = NULL;
			list->tail = NULL;
		}
		data = temp->data;
		free(temp);
		list->count--;
		if (list->count == 1) {
			list->tail = list->head;
		}
	}
	
	return data;
}

void * slist_remove_tail(slist * list)
{
	void *data = NULL;

	if (list->tail) {
		snode *current, *previous = NULL;
		current = list->head;
		while (current->next) {
			previous = current;
			current = current->next;
		}
		data = current->data;
		free(current);
		if (previous) {
			previous->next = NULL;
		}
		else {
			/* List is now empty */
			list->head = NULL;
			list->tail = NULL;
		}
		list->count--;
		if (list->count == 1) {
			list->head = list->tail;
		}
	}

	return data;
}

void * slist_remove(slist *list, snode *node, snode *previous)
{
	void *data;
	if (node == list->head) {
		data = slist_remove_head(list);
	}
	else {
		previous->next = node->next;
		data = node->data;
		list->count--;
		if (list->count == 1) {
			list->tail = list->head;
		}
		else if (node == list->tail) {
			list->tail = previous;
		}
		free(node);
	}
	return data;
}

void slist_insert_before(slist * list, snode * node, snode * previous, void * data)
{
	if (node == list->head) {
		slist_add_head(list, data);
	}
	else {
		snode * newnode = snode_create(data);
		newnode->next = node;
		previous->next = newnode;
		list->count++;
	}
}

snode * slist_insert_after(slist * list, snode * node, void * data)
{
	snode * newnode;
	if (node == NULL) {
		slist_add_head(list, data);
		newnode = list->head;
	}
	else {
		newnode = snode_create(data);
		if (newnode) {
			newnode->next = node->next;
			node->next = newnode;
			if (node == list->tail) {
				list->tail = newnode;
			}
		}
		list->count++;
	}
	return newnode;
}

void slist_for_each(const slist * list, slist_forfn fun)
{
	snode * node;
	for (node = list->head; node != NULL; node = node->next) {
		fun(node->data);
	}
}

unsigned int slist_get_count(const slist * list)
{
	return list->count;
}

An example program:

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

#include <slist.h>

int main(void)
{
    slist * list = slist_create();
    char * elements[] = {"A", "B", "C", "D", "E", "F"};
    const unsigned int n = sizeof(elements) / sizeof(const char*);
    unsigned int i;
    snode * node, * previous = NULL;
    unsigned int found = 0;

    /* Populate the list with A, B, ..., F */
    for (i = 0; i < n; i++) {
        slist_add_tail(list, elements[i]);
    }
    
    /* Insert X and Y either side of C */
    for (node = list->head; node != NULL && !found; node = node->next) {
        if (strcmp((const char*)node->data, "C") == 0) {
            slist_insert_before(list, node, previous, "X");
            slist_insert_after(list, node, "Y");
            found = 1;
        }
        previous = node;
    }

    /* Forward iteration */
    for (node = list->head; node != NULL; node = node->next) {
        printf("%s\n", (const char*)node->data);
    }

    slist_delete(list);

    return 0;
}

Linked list in C

This is a doubly-linked list implementation. A linked list allows easy insertion and removal at either end or in the middle. Being doubly-linked allows traversal in reverse as well as forwards.

Here is an example program:

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

#include <linkedlist.h>

int main(void)
{
    linkedlist * list = linkedlist_create();
    char * elements[] = {"A", "B", "C", "D", "E", "F"};
    const unsigned int n = sizeof(elements) / sizeof(const char*);
    unsigned int i;
    listnode * node;
    unsigned int found = 0;

    /* Populate the list with A, B, ..., F */
    for (i = 0; i < n; i++) {
        linkedlist_add_tail(list, elements[i]);
    }
    
    /* Insert X and Y either side of C */
    for (node = list->head; node != NULL && !found; node = node->next) {
        if (strcmp((const char*)node->data, "C") == 0) {
            linkedlist_insert_before(list, node, "X");
            linkedlist_insert_after(list, node, "Y");
            found = 1;
        }
    }

    /* Forward iteration */
    for (node = list->head; node != NULL; node = node->next) {
        printf("%s\n", (const char*)node->data);
    }
    putchar('\n');

    /* Reverse iteration */
    for (node = list->tail; node != NULL; node = node->previous) {
        printf("%s\n", (const char*)node->data);
    }
    
    linkedlist_delete(list);

    return 0;
}

The header file:

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

struct listnode {
	struct listnode * next;
	struct listnode * previous;
	void * data;
};
typedef struct listnode listnode;

struct linkedlist {
	listnode * head;
	listnode * tail;
	unsigned int count;
};
typedef struct linkedlist linkedlist;

typedef void (*linkedlist_forfn)(void *);

linkedlist * linkedlist_create(void);
void linkedlist_empty(linkedlist * list);
void linkedlist_delete(linkedlist * list);
void linkedlist_add_head(linkedlist * list, void * data);
void linkedlist_add_tail(linkedlist * list, void * data);
void linkedlist_insert_before(linkedlist * list, listnode * node, void * data);
void linkedlist_insert_after(linkedlist * list, listnode * node, void * data);
void * linkedlist_remove_head(linkedlist * list);
void * linkedlist_remove_tail(linkedlist * list);
void * linkedlist_remove_node(linkedlist * list, listnode * node);
void linkedlist_for_each(const linkedlist * list, linkedlist_forfn fun);
unsigned int linkedlist_get_count(const linkedlist * list);

#endif /* LINKEDLIST_H */

The implementation:

#include <stdlib.h>

#include <linkedlist.h>

listnode * listnode_create(void * data)
{
	listnode * node = malloc(sizeof(listnode));
	if (node) {
		node->next = NULL;
		node->previous = NULL;
		node->data = data;
	}
	return node;
}

linkedlist * linkedlist_create(void)
{
	linkedlist * list = malloc(sizeof(linkedlist));
	if (list) {
		list->head = NULL;
		list->tail = NULL;
		list->count = 0;
	}
	return list;
}

void linkedlist_empty(linkedlist * list)
{
	while(list->head != NULL) {
		linkedlist_remove_tail(list);
    }
}

void linkedlist_delete(linkedlist * list)
{
	if (list) {
		linkedlist_empty(list);
		free(list);
	}
}

void linkedlist_add_head(linkedlist * list, void * data)
{
	listnode * node;
	node = listnode_create(data);
	if (list->head != NULL) {
		list->head->previous = node;
		node->next = list->head;
		list->head = node;
	}
	else {
		list->head = node;
		list->tail = node;
	}
	list->count++;
}

void linkedlist_add_tail(linkedlist * list, void * data)
{
	listnode * node;
	node = listnode_create(data);
	if (list->tail != NULL) {
		list->tail->next = node;
		node->previous = list->tail;
		list->tail = node;
	}
	else {
		list->head = node;
		list->tail = node;
	}
	list->count++;
}

void linkedlist_insert_before(linkedlist * list, listnode * node, void * data)
{
	listnode * newnode;
	if (node == list->head) {
		linkedlist_add_head(list, data);
	}
	else {
		newnode = listnode_create(data);
		newnode->next = node;
		newnode->previous = node->previous;
		node->previous->next = newnode;
		node->previous = newnode;
		list->count++;
	}
}

void linkedlist_insert_after(linkedlist * list, listnode * node, void * data)
{
	listnode * newnode;
	if (node == list->tail) {
		linkedlist_add_tail(list, data);
	}
	else {
		newnode = listnode_create(data);
		newnode->previous = node;
		newnode->next = node->next;
		node->next->previous = newnode;
		node->next = newnode;
		list->count++;
	}
}

void * linkedlist_remove_head(linkedlist * list)
{
	void * data = NULL;
	if (list->head != NULL) {
		listnode * temp = list->head;
		list->head = list->head->next;
		if (list->head == NULL) {
			list->tail = NULL;
		}
		else {
			list->head->previous = NULL;
			if (list->head->next != NULL) {
				list->head->next->previous = list->head;
			}
			else {
				list->tail = list->head;
			}
		}
		data = temp->data;
		free(temp);
		list->count--;
	}
	return data;
}

void * linkedlist_remove_tail(linkedlist * list)
{
	void * data = NULL;
	if (list->tail != NULL) {
		listnode * temp = list->tail;
		list->tail = list->tail->previous;
		if (list->tail == NULL) {
			list->head = NULL;
		}
		else {
			list->tail->next = NULL;
			if (list->tail->previous != NULL) {
				list->tail->previous->next = list->tail;
			}
			else {
				list->head = list->tail;
			}
		}
		data = temp->data;
		free(temp);
		list->count--;
	}
	
	return data;
}

void * linkedlist_remove_node(linkedlist * list, listnode * node)
{
	void * data;
	if (node == list->head) {
		data = linkedlist_remove_head(list);
	}
	else if (node == list->tail) {
		data = linkedlist_remove_tail(list);
	}
	else {
		node->previous->next = node->next;
		node->next->previous = node->previous;
		data = node->data;
		free(node);
		list->count--;
	}
	return data;
}

void linkedlist_for_each(const linkedlist * list, forfn fun)
{
	listnode * node;
	for (node = list->head; node != NULL; node = node->next) {
		fun(node->data);
    }
}

unsigned int linkedlist_get_count(const linkedlist * list)
{
	return list->count;
}

Finding out if a binary tree is a binary search tree recursively

A binary tree is a binary search tree (BST) if for every node, its left child’s value is less than its value, and its right child’s value is greater than its value.

This lends itself to a simple recursive algorithm for finding out if a binary tree is a BST.

unsigned int binarytree_is_bst_recursive(const btnode *node, int (*compare)(const void*, const void*))
{
    return 
        (node->left == NULL || 
        (compare(node->left->data, node->data) < 0 && binarytree_is_bst_recursive(node->left, compare)))
        &&
        (node->right == NULL ||
        (compare(node->right->data, node->data) > 0 && binarytree_is_bst_recursive(node->right, compare)));
}

unsigned int binarytree_is_bst(const binarytree *tree)
{
    unsigned int bst = 1;
    if (tree->root) {
        bst = binarytree_is_bst_recursive(tree->root, tree->compare);
    }
    return bst;
}