Tag Archives: Binary Tree

Huffman coding in C

Huffman coding is a compression method which generates variable-length codes for data – the more frequent the data item, the shorter the code generated. This allows more efficient compression than fixed-length codes. This is an implementation of the algorithm in C. The function huffman() takes arrays of letters and their frequencies, the length of the arrays, and a callback which is called for each code generated. The algorithm requires a priority queue, and I used a min-heap for the purpose.

#include <stdlib.h>

#include <minheap.h>

struct huffman_node {
    char data;
    unsigned int frequency;
    struct huffman_node *left;
    struct huffman_node *right;
};
typedef struct huffman_node huffman_node;

huffman_node *huffman_node_create(char data, unsigned int frequency)
{
    huffman_node *node = malloc(sizeof(huffman_node));
    if (node) {
        node->data = data;
        node->frequency = frequency;
        node->left = NULL;
        node->right = NULL;
    }
    return node;
}

void huffman_node_delete(huffman_node *node)
{
    if (node) {
        huffman_node_delete(node->left);
        huffman_node_delete(node->right);
        free(node);
    }
}

unsigned int max(unsigned int a, unsigned int b)
{
    return a > b ? a : b;
}

unsigned int huffman_node_height(const huffman_node *node)
{
    unsigned int height = 0;
    if (node->left || node->right) {
        height = max(node->left ? huffman_node_height(node->left) : 0,
                node->right ? huffman_node_height(node->right) : 0) + 1;
    }
    return height;
}

void huffman_node_print(const huffman_node *node, unsigned int indent)
{
    unsigned int i;
    for (i = 0; i < indent; i++) {
        printf("  ");
    }
    printf("%c %u\n", node->data, node->frequency);
    if (node->left != NULL) {
        huffman_node_print(node->left, indent + 1);
    }
    if (node->right != NULL) {
        huffman_node_print(node->right, indent + 1);
    }
}

typedef void huffmanfn(char, const unsigned int *, size_t);

void huffman_node_encodings(const huffman_node *node, unsigned int *arr, 
        unsigned int pos, huffmanfn fun)
{
    if (node->left) {
        arr[pos] = 0;
        huffman_node_encodings(node->left, arr, pos + 1, fun);
    }
    if (node->right) {
        arr[pos] = 1;
        huffman_node_encodings(node->right, arr, pos + 1, fun);
    }
    if (!(node->left || node->right)) {
        fun(node->data, arr, pos);
    }
}

void huffman(const char *letters, const int *frequencies, size_t size, huffmanfn fun)
{
    minheap *heap = minheap_create();
    unsigned int i;
    huffman_node *top;
    unsigned int *arr;
    /* Populate the heap */
    for (i = 0; i < size; i++) {
        minheap_add(heap, huffman_node_create(letters[i], frequencies[i]), frequencies[i]);
    }
    /* Build the tree */
    while (minheap_get_count(heap) != 1) {
        huffman_node *left = minheap_remove_min(heap);
        huffman_node *right = minheap_remove_min(heap);
        top = huffman_node_create('$', left->frequency + right->frequency);
        top->left = left;
        top->right = right;
        minheap_add(heap, top, top->frequency);
    }
    top = minheap_remove_min(heap);
    /* Generate the encodings */
    arr = malloc(huffman_node_height(top) * sizeof(unsigned int));
    huffman_node_encodings(top, arr, 0, fun);
    /* Clean up */
    huffman_node_delete(top);
    free(arr);
    minheap_delete(heap);
}

Example program:

void print(char letter, const unsigned int *arr, size_t len)
{
    unsigned int i;
    printf("%c: ", letter);
    for (i = 0; i < len; i++) {
        printf("%u", arr[i]);
    }
    putchar('\n');
}

int main(void)
{
    char letters[] = {'a', 'b', 'c', 'd', 'e', 'f'};
    int frequencies[] = {45, 13, 12, 16, 9, 5};
    const size_t size = sizeof(letters) / sizeof(letters[0]);
    huffman(letters, frequencies, size, print);
    return 0;
}

The output:

a: 0
c: 100
b: 101
f: 1100
e: 1101
d: 111

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;
}

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;
}

Finding out if a binary search tree is AVL recursively

A binary search tree with the AVL property has no node whose left and right heights differ by more than 1. AVL trees maintain this property by maintaining balance information in their nodes, and rebalancing themselves when they find the property has been violated.
It is possible, however, to determine whether a tree without any balance information has the AVL property by a depth-first search of the tree, checking the property at every node and propagating the result upwards.

typedef struct {
	unsigned int height;
	unsigned int avl;
} avl_info;

avl_info binarytree_avl_recursive(const btnode *node)
{
	avl_info info;
	info.height = 0;
	info.avl = 1;
	unsigned int leftheight = 0, rightheight = 0;
    if (node->left || node->right) {
        unsigned int leftavl = 1, rightavl = 1;
        avl_info child_info;
        if (node->left) {
            child_info = binarytree_avl_recursive(node->left);
            leftheight = child_info.height + 1;
            leftavl = child_info.avl;
        }
        if (node->right) {
            child_info = binarytree_avl_recursive(node->right);
            rightheight = child_info.height + 1;
            rightavl = child_info.avl;
        }
        if (leftheight > rightheight) {
            info.height = leftheight;
        } 
        else {
            info.height = rightheight;
        }
        info.avl = leftavl && rightavl && abs(leftheight - rightheight) <= 1;
    }
	return info;
}

unsigned int binarytree_avl(const binarytree *tree)
{
    unsigned int result = 1;
    if (tree->root != NULL) {
        result = binarytree_avl_recursive(tree->root).avl;
    }
    return result;
}

Counting internal nodes in a binary tree recursively

This is the counterpart of counting leaves in a binary tree recursively. If we are an internal node, we count 1 for ourselves, then recurse into the left and right subtrees and sum the count of internal nodes in them.

unsigned int binarytree_count_internal_nodes_recursive(const btnode *root)
{
    unsigned int count = 0;
    if (root->left != NULL || root->right != NULL) {
        count = 1;
        if (root->left != NULL) {
		    count += binarytree_count_internal_nodes_recursive(root->left);
	    }
        if (root->right != NULL) {
            count += binarytree_count_internal_nodes_recursive(root->right);
        }
    }
	return count;
}

unsigned int binarytree_count_internal_nodes(const binarytree *tree)
{
    unsigned int count = 0;
    if (tree->root != NULL) {
	    count = binarytree_count_internal_nodes_recursive(tree->root);
    }
    return count;
}

Counting leaves in a binary tree recursively

This is another recursive algorithm. If we are a leaf node, we return 1, and if not, we recurse into the left and right subtrees and return the sum of the leaves in them.

unsigned int binarytree_count_leaves_recursive(const btnode *root)
{
    unsigned int count = 0;
    if (root->left == NULL && root->right == NULL) {
        count = 1;
    }
    else {
        if (root->left != NULL) {
		    count += binarytree_count_leaves_recursive(root->left);
	    }
        if (root->right != NULL) {
            count += binarytree_count_leaves_recursive(root->right);
        }
    }
	return count;
}

unsigned int binarytree_count_leaves(const binarytree *tree)
{
    unsigned int count = 0;
    if (tree->root != NULL) {
	    count = binarytree_count_leaves_recursive(tree->root);
    }
    return 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;
}

Finding the minimum depth of a binary tree recursively

This is the counterpart of finding the height of a binary tree recursively. We start with a depth of 0, and only if a node has 2 children, we add the minimum of their depths.

static int min(int a, int b)
{
    if (a <= b) {
        return a;
    }
    return b;
}

unsigned int binarytree_minimum_depth_recursive(const btnode *node)
{
    unsigned int depth = 0;
    if (node->left && node->right) {
        depth = min(binarytree_minimum_depth_recursive(node->left), 
                binarytree_minimum_depth_recursive(node->right)) + 1;
    }
    return depth;
}

unsigned int binarytree_minimum_depth(const binarytree *tree)
{
    unsigned int depth = 0;
    if (tree->root) {
        depth = binarytree_minimum_depth_recursive(tree->root);
    }
    return depth;
}

Sorting a linked list by turning it into a binary search tree

Introduction

A doubly-linked list node has two pointers, previous and next, and a binary tree node also has two pointers, left and right

This means that one way of sorting a linked list is to turn it into a binary tree and then back into a list again.

Turning the list into a binary tree

Turning the list into a tree is just a question of iterating over the list and performing the normal binary tree insertion algorithm. We need to remember to save the current node’s next pointer before we insert it, as it will not be available afterwards.

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

listnode * linkedlist_to_tree(linkedlist * list, cmpfn compare)
{
    listnode * root = list->head;
    if (root) {
        listnode * node = root->next;
        root->previous = NULL;
        root->next = NULL;
        while (node != NULL) {
            listnode * next = node->next;
            listnode * current = root, * previous = NULL;
            int result;
            while (current != NULL) {
                previous = current;
                result = compare(current->data, node->data);
                if (result > 0) {
                    current = current->previous;
                }
                else {
                    current = current->next;
                }
            }
            if (result > 0) {
                previous->previous = node;
            }
            else {
                previous->next = node;
            }
            node->previous = NULL;
            node->next = NULL;
            node = next;
        }
    }
    return root;
}

Turning the binary tree back into a list

This involves an inorder traversal of the tree, which is most easily implemented using recursion. We need to look out for the first and last elements; they need to be treated specially as they are the head and tail of the list.

The first element in a binary tree is the one that we encounter the first time we can go left no further. We find the last element by keeping track of the number of elements encountered so far, and comparing it to the number in the list.

void linkedlist_from_tree(linkedlist * list, listnode * root,
        listnode ** previous, unsigned int * count)
{
    if (root) {
        listnode * left = root->previous;
        listnode * right = root->next;
        linkedlist_from_tree(list, left, previous, count);
        if (root->previous == NULL && list->head == NULL) {
            /* We're at the first element */
            list->head = root;
            list->head->previous = NULL;
        }
        else {
            (*previous)->next = root;
            root->previous = *previous;
        }
        if (*count == linkedlist_get_count(list) - 1) {
            /* We're at the last element */
            list->tail = root;
            list->tail->next = NULL;
        }
        *previous = root;
        (*count)++;
        linkedlist_from_tree(list, right, previous, count);
    }
}

The sort function

Our linked list sort function now just needs to combine the two operations:

void linkedlist_sort(linkedlist * list, cmpfn compare)
{
    unsigned int count = 0;
    listnode * previous;
    listnode * tree = linkedlist_to_tree(list, compare);
    list->head = NULL;
    list->tail = NULL;
    linkedlist_from_tree(list, tree, &previous, &count);
}

Example program

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

    list = linkedlist_create();
    for (i = 0; i < n; i++) {
        linkedlist_add_tail(list, elements[i]);
    }
    linkedlist_sort(list, (cmpfn)strcmp);
    linkedlist_for_each(list, (forfn)puts);
    linkedlist_delete(list);

    return 0;
}

Finding the height of a binary tree recursively

The height of a node in a binary tree is simply the maximum of the height of its left and right subtrees, plus one.

This lends itself to a simple recursive algorithm for finding the height of a binary tree.

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;
}