Simple tree dictionary structure in C

Question

I have developed a C library whose goal is to store strings in an easily searchable tree structure (which I have dubbed tree-dictionary). I come from a math background and I have been coding in Python for a few months, but I am a still a complete beginner to C and this is my first non-trivial project in the language. My goal was to learn the basics of C syntax, non-OOP programming, and hands-on memory management.

Here comes the code:

/**
 * @file treedict.h
 * @author
 * @brief Define a tree dictionary that stores words using a tree data structure.
 * 
 * The dictionary will only have three basic functionalities: it will be able to store a word, to check
 * if a word is in it, and, finally, to delete a word.
 * 
 * The dictionary is defined in three steps: first, define the nodes of the tree and the related functions.
 * Then, define the functions that work with the whole tree.
 * Finally, define the functions that use the tree as a dictionary.
 * 
 * Internally, each word is represented as a sequence of consecutive nodes originating at the root of the
 * tree. Each node contains a letter and the last letter is marked as an end-of-word node. 
 * A single node of the tree may contain a letter belonging to more than one word. The words are added
 * in such a way that the number of nodes is minimized.
 * 
 * Example: a dictionary that contains the words "ant", "antilope", "animal" and "animalistic" 
 * can be represented as follows:
 * 
 * a n
 *     i m a l E
 *             i s t i c E
 *     t E
 *       i l o p e E   
 * 
 * The root of a tree dictionary is supposed to be a node containing the null character '\0'.
 */

#ifndef TREEDICT_H
#define TREEDICT_H

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

/*********************************** NODE DEFINITION ****************************/

/**
 * @struct Node
 * @brief Datatype for the nodes of the tree.
 */
struct Node
{
    struct Node **children; /*< Array of pointers to the children of the node. */
    int length_of_children_array; /*< Length of allocated children array 
                                    (NB: this is not the number of children, just the memory allocated for
                                    their pointers.) 
                                */
    int number_of_children; /*< Number of children of the node. */

    char letter; /*< Letter represented by the node. */
    bool is_end_of_word; /*< Bool marking whether this is an end-of-word node or not. */
};
typedef struct Node Node;

/*********************************** NODE FUNCTIONS ****************************/

/**
 * @brief Initialize a new node instance.
 * 
 * @param letter 
 * Letter of the created node.
 * @return Node* 
 * Pointer to the created node.
 */
Node *create_node(char letter);

/**
 * @brief Free a node and its children array from memory. 
 * 
 * @param node
 */
void delete_node(Node *node);

/**
 * @brief Add child node to parent node.
 * 
 * @param child 
 * @param parent
 */
void add_child(Node *parent, Node *child);

/**
 * @brief Check if a node has children or not.
 * 
 * @param node 
 * @return true 
 * @return false 
 */
bool is_leaf(Node *node);

/**
 * @brief Reallocate children array of the given node to the be as long as the number of children.
 * 
 * @param node 
 */
void resize_children_array(Node *node);

/*********************************** TREE FUNCTIONS ****************************/

/**
 * @brief Free a whole tree from memory by freeing each node recursively, starting from the leaves.
 * 
 * @param root 
 * Pointer to the root of the tree.
 */
void delete_tree(Node *root);

/**
 * @brief Print a text representation of a tree to screen.
 * 
 * @param root 
 * Pointer to the root of the tree.
 */
void print_tree(Node *root);

/**
 * @brief Remove a whole branch recursively from its parent and free it from memory.
 * 
 * @param parent 
 * Pointer to the parent.
 * @param index_of_child 
 * parent->children[index_of_child] is supposed to point to the root of the branch that is to be deleted.
 */
void delete_branch(Node *parent, int index_of_child);

/*********************************** TREE DICTIONARY FUNCTIONS ****************************/

/**
 * @brief Add a word to a tree dictionary.
 * 
 * @param dict 
 * Pointer to the root of the dictionary.
 * @param word 
 * Pointer to string representing the word.
 */
void add_word(Node *dict, const char *word);

/**
 * @brief Check if a tree dictionary contains a word.
 * 
 * @param dict 
 * Pointer to the root of the dictionary.
 * @param word 
 * Pointer to string representing the word.
 * @return true 
 * @return false 
 */
bool contains_word(Node *dict, const char *word);

/**
 * @brief Delete a word from a tree dictionary.
 * 
 * @param dict 
 * Pointer to the root of the dictionary.
 * @param word 
 * Pointer to string representing the word.
 */
void delete_word(Node *dict, const char *word);

#endif

/**
 * @file treedict.c
 * @author
 * @brief Code for treedict.h.
 * 
 * 
 * 
 */
#include "treedict.h"

/*********************************** NODE DEFINITION ****************************/

/**
 * @brief Default length the the node.children array in a newly created node.
 */
static const int DEFAULT_LENGTH_OF_CHILDREN_ARRAY = 32;

/*********************************** NODE FUNCTIONS ****************************/

/* 
    Allocate memory for a new node instance and initialize its attributes before returning a pointer
    to the user. 
*/
Node *create_node(char letter) {
    Node *node = (Node *)calloc(1,sizeof(Node));

    node->children = (Node **)malloc(DEFAULT_LENGTH_OF_CHILDREN_ARRAY*sizeof(Node*));
    node->length_of_children_array = DEFAULT_LENGTH_OF_CHILDREN_ARRAY;
    node->letter = letter;

    return node;
}

/*
    Free the children array of the given node from memory and then free the node itself.
*/
void delete_node(Node *node) {
    free(node->children);
    free(node);
}

/*
    Add a child node to a parent node. If the children array is full, reallocate it with twice its length. 
*/
void add_child(Node *parent, Node *child) {
    if (parent->number_of_children == parent->length_of_children_array) {
        parent->children = (Node **)realloc(parent->children, 2*parent->length_of_children_array*sizeof(Node *));
        parent->length_of_children_array *= 2;
    }

    parent->children[parent->number_of_children] = child;
    ++parent->number_of_children;
}

/*
    Check if a child is a leaf.
*/
bool is_leaf(Node *node) {
    return node->number_of_children == 0;
}

void resize_children_array(Node *node) {
    node->children = (Node **)realloc(node->children, node->number_of_children*sizeof(Node *));
    node->length_of_children_array = node->number_of_children;
}


/*********************************** TREE FUNCTIONS ****************************/

/*
    Recursively delete a whole tree.
*/
void delete_tree(Node *root) {
    int i;

    for (i = 0; i < root->number_of_children; i++)
        delete_tree(root->children[i]);

    delete_node(root);
}

/*
    If the child has any children, the branch of the tree starting with the child is
    recursively deleted and its memory is freed.
*/
void delete_branch(Node *parent, int index_of_child){
    int i;
    delete_tree(parent->children[index_of_child]);

    for(i = index_of_child; i < parent->number_of_children-1; i++)
        parent->children[i] = parent->children[i+1];

    parent->number_of_children--;
}

/* 
    Helper function that actually does the recursion for the print_tree function below.

    branch is a pointer that keeps track of the node of the tree we are at.
    depth tells us how deep we are in the tree.

    Represent the depth by printing an equal number of dots. Then, print the current letter. If
    we are at an end-of-word node, print E. Print a new-line.
    Finally, call print_branch at all the children of the current node with an incremented depth.
*/
void print_branch(Node* branch, int depth) {
    int i,j;

    for (j = 0; j < depth; j++)
        printf(".");

    if (branch->is_end_of_word)
        printf("%c E\n", branch->letter);
    else
        printf("%c\n", branch->letter);

    for (i = 0; i < branch->number_of_children; i++)
        print_branch(branch->children[i], depth+1);
}

void print_tree(Node *root) {
    print_branch(root, 0);
}


/*********************************** TREE DICTIONARY FUNCTIONS ****************************/

void add_word(Node *dict, const char *word) {
    /* i = string index, j = children index */
    int i = 0, j;
    bool matching_child_found;
    Node *current_node = dict;
    
    /* Travel along the branches of the dictionary to find the end of the longest
    prefix of word contained in the dictionary. */
    while (true) {
        matching_child_found = false;

        for (j = 0; j < current_node->number_of_children; j++)
            if ((current_node->children[j])->letter == word[i]) {
                current_node = current_node->children[j];
                matching_child_found = true;
                i++;
                break;
            }
        
        if (!matching_child_found) break;
        if (word[i] == '\0') break;
    }

    /* If we have found a child that matches the last character of the word, it suffices to
    mark it as an end-of-word character. Otherwise, if the last found character is not the last
    character of the word, add one node for each of the following characters and mark the last
    as an end-of-word character. */
    if (matching_child_found)
        current_node->is_end_of_word = true;
    else {
        Node *new_node;
        for (; word[i] != '\0'; i++) {
            new_node = create_node(word[i]);
            add_child(current_node, new_node);
            current_node = new_node;
        }
        current_node->is_end_of_word = true;
    }
}

/* 
    Travel along the branches of the dictionary comparing the letter of each child of 
    current node to word[i]. If no matching child is found, return false. If a matching child
    is found for the last letter of word, check whether it is an end-of-word node.
    If it is, return true. If it isn't, return false.
*/
bool contains_word(Node *dict, const char *word){
    /* i = string index, j = children index */
    int i = 0, j;
    bool matching_child_found;
    Node *current_node = dict;
    
    /* Travel along the branches of the dictionary comparing the letter of each child of 
    current node to word[i]. */
    while (true) {
        matching_child_found = false;

        for (j = 0; j < current_node->number_of_children; j++)
            if ((current_node->children[j])->letter == word[i]) {
                current_node = current_node->children[j];
                matching_child_found = true;
                i++;
                break;
            }
        
        /* If no mathing child is found word is no in the dictionary. */
        if (!matching_child_found) return false;
        /* If a node matching the last character of word is found, the word is in the dictionary
        if and only if the node is an end-of-word node. */
        if (word[i] == '\0') return current_node->is_end_of_word;
    }
}

/* 
     If no matching child is found, the word is not in the dictionary
    and thus we can return.
    
    If we find the node containing the last letter of word, if such node is marked as an end-of-word 
    node, and if such node has no children, we will deleted the entire branch with root node 
    "parent_of_branch_to_delete->children[index_of_branch_to_delte]", 
    as these nodes would become redundant.
    On the other hand, we find the node containing the last letter of word but the node has children,
    no node needs to be deleted and it suffices to set current_node->is_end_of_word = false.
*/
void delete_word(Node *dict, const char *word) {
    /* i = string index, j = children index */
    int i = 0, j, index_of_branch_to_delete;
    Node *current_node = dict, *parent_of_branch_to_delete = NULL;
    bool matching_child_found;

    /* Travel along the branches of the dictionary comparing the letter of each child of 
    current node to word[i]. */
    while (true) {
        matching_child_found = false;

        for (j = 0; j < current_node->number_of_children; j++)
            if ((current_node->children[j])->letter == word[i]) {
                /* Keep track of the last node encountered with more than 1 child and keep track of the index
                that the subsequent branch we travel along has in its children array (parent_of_branch_to_delete 
                and index_of_branch_to_delete) respectively. */
                if (current_node->number_of_children > 1) { 
                    parent_of_branch_to_delete = current_node;
                    index_of_branch_to_delete = j;
                }

                matching_child_found = true;
                current_node = current_node->children[j];
                i++;
                break;
            }

        /* If no matching child is found, we can return because the word is not 
        in the dictionary in the first place. */
        if (!matching_child_found) return;

        /* If a node containing the last character of the string is found, but it is not marked as
        an end_of_word node, the word is not in the dictionary and we can thus return. */
        if (word[i] == '\0' && !current_node->is_end_of_word) return;

        /* If a node containing the last character of the string is found and such node is marked as
        an end-of-word node, the word is in the dictionary and we can procced 
        break out of the loop and remove it. */
        if (word[i] == '\0' && current_node->is_end_of_word) break;
    }

    /* If current_node has children, it suffices to unmark it as an end-of-word node but no node
    needs to be deleted as every node we have iterated along is part of other words and is not redundant.
    If current_node has no children, the entire branch is sits on needs 
    to be remove at its last bifurcation. 
    */
    if (current_node->number_of_children > 0)
        current_node->is_end_of_word = false;
    else
        delete_branch(parent_of_branch_to_delete, index_of_branch_to_delete);
}

I have done some simple unit testing with words loaded from a .txt file and everything seems to be working fairly well, but I would appreciate it very much if someone more experienced than me could take a look at my code and confirm that I'm on the right path. My main concerns are:

1. Although C is not geared towards OOP programming, I find it very hard not to think in terms of objects, methods and attributes. I know that OOP is not a language paradigm but a programming paradigm... still, I'm not sure whether this is the best approach to C programming. Does my code look like native C to you, or does it look like I am translating from Python to C in my head?
2. Is my code memory safe? Am I leaking memory somewhere? I have written deleter functions both for trees and nodes and I have tried to have them handle garbage collection. Is this recommended? Have I used
3. I have used a Doxygen extension for vscode to generate docstrings. Is this appropriate? Is my code readable? Is it good practice to put API documentation in .h files and implementation documentation in .c files?
4. Does the way I have divided the code between treedict.h and treedict.c make sense? Am I putting header files and the preprocessor to good use?

I'm following the C89 standard. I know that C99 is a bit nicer (one-line comments and all...), but my school still uses C89 and I will be required to write assignments in C89 in the next few months, so I've decided to practice C89.

PS: bool.h just defines bool as an enum.

/**
 * @file bool.h
 * @author
 * @brief Custom definition for Boolean datatype.
 * 
 */
#ifndef BOOL_H
#define BOOL_H

typedef enum { false, true } bool;

#endif

Answer 1

Hide the implementation:

Node should be an opaque data type defined in the source file. The header file would then only contain the forward declaration, and the prototypes for the APIs:

#ifndef TREEDICT_H
#define TREEDICT_H

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

/*********************************** NODE DEFINITION ****************************/

struct Node;

/*********************************** NODE FUNCTIONS ****************************/
...
Node *create_node(char letter);
...

and in the source file:

struct Node {
    struct Node **children; /*< Array of pointers to the children of the node. */
    int length_of_children_array; /*< Length of allocated children array 
                                    (NB: this is not the number of children, just the memory allocated for
                                    their pointers.) 
                                */
    int number_of_children; /*< Number of children of the node. */

    char letter; /*< Letter represented by the node. */
    bool is_end_of_word; /*< Bool marking whether this is an end-of-word node or not. */
};

See: What defines an opaque type in C, and when are they necessary and/or useful?

Do not cast the return of malloc() and family:

Starting with C89, malloc() and family returns a generic void * (as compared to the char * it originally used to) that is implicitly converted to any other pointer type (the cast is redundant, no need to clutter the codebase).

#if 0
Node *node = (Node *)calloc(1,sizeof(Node));
#else
// Take the size from the variable rather than its type to reduce the chance of a mismatch.
Node *const node = calloc(1, sizeof *node);
#endif

Side-note: Is there any specific reason you used calloc() for node but malloc() for node->children?

Check the return value of library functions:

If a function be advertised to return an error code in the event of difficulties, thou shalt check for that code, yea, even though the checks triple the size of thy code and produce aches in thy typing fingers, for if thou thinkest ''it cannot happen to me'', the gods shall surely punish thee for thy arrogance. - The Ten Commandments for C Programmers

According to the C17 standard:

The malloc function returns either a null pointer or a pointer to the allocated space.

Failing to check for it risks invoking undefined behavior by a subsequent null pointer dereference.

#if 0
    Node * node = (Node *)calloc(1,sizeof(Node));

    node->children = (Node **)malloc(DEFAULT_LENGTH_OF_CHILDREN_ARRAY*sizeof(Node*));
#else
    Node *const node = calloc(1, sizeof *node);

    if (!node) {
        return NULL;
    }

    node->children = malloc(DEFAULT_LENGTH_OF_CHILDREN_ARRAY * sizeof node->children[0]);
    
    if (!node->children) {
        free(node);
        return NULL;
    }
    ...
}
#endif

Use braces around if/while/for statement et cetera:

I suggest always using:

if (current_node->number_of_children > 0) {
    current_node->is_end_of_word = false;
} else {
    delete_branch(parent_of_branch_to_delete, index_of_branch_to_delete);
}

to

if (current_node->number_of_children > 0)
    current_node->is_end_of_word = false;
else
    delete_branch(parent_of_branch_to_delete, index_of_branch_to_delete);

The problem with the second version is that if you go back and add a second statement to the if or else clause without adding the curly braces, your code will break. See: Apple's SSL/TLS bug.

Use size_t for sizes, cardinalities, and ordinal numbers:

int length_of_children_array; /*< Length of allocated children array 
                                    (NB: this is not the number of children, just the memory allocated for
                                    their pointers.) 
                                */
int number_of_children; /*< Number of children of the node. */

The length_of_children_array and number_of_children can not be negative. Consider using size_t or some other unsigned type.

Minor:

/*
    Free the children array of the given node from memory and then free the node itself.
*/
void delete_node(Node *node) {
    free(node->children);
    free(node);
}

I don't think this comment adds any value to the code. It is perfectly clear what delete_node() does. Consider removing it.

Answer 2

While the answer by Harith addresses very valid points, I feel that there is some repetition in this code that deserves to be eliminated. In particular, you see the following pattern arise a lot:

while (true) {
    matching_child_found = false;

    for (j = 0; j < current_node->number_of_children; j++)
        if ((current_node->children[j])->letter == word[i]) {
            current_node = current_node->children[j];
            matching_child_found = true;
            i++;
            break;
        }
    
    if (!matching_child_found) break;
    if (word[i] == '\0') break;
}

This could be simplified by extracting the common functionality of finding a child (inner loop), and following a path through the tree (outer loop). One way to achieve this could be for instance the following two helper functions (untested):

// Finds the child with letter `letter`
static Node* find_child(Node* node, char letter) {
    for (size_t i = 0; i < node->number_of_children; i++) {
        if (node->children[i]->letter == letter)
            return node->children[i];
    }
    return NULL;
}

// Traverses the tree from `node` using the path determined by `prefix`.
// Stops when the node has no child or when the end of the prefix has been found.
static void find_longest_prefix(Node** node, const char** prefix) {
    while (**prefix) {
        Node* child = find_child(*node, **prefix);
        if (!child)
            return;
        *node = child;
        *prefix = (*prefix) + 1;
    }
}

These can be static and remain private, if you want to keep these a detail of the implementation. Now, with those two functions, you can implement contains_word and add_word like this:

bool contains_word(Node* node, const char* word) {
    find_longest_prefix(&node, &word);
    return *word == 0 && node->is_end_of_word;
}

bool add_word(Node* node, const char* word) {
    find_longest_prefix(&node, &word);
    while (*word) {
        Node* child = create_child(*word);
        add_child(node, child);
        node = child;
        word++;
    }
    bool already_exists = node->is_end_of_word;
    node->is_end_of_word = true;
    return !already_exists;
}

I will leave rewriting the rest of the implementation using those helpers as an exercise.

Answer 3

Less "chaff", please!

Downloaded and concatenated the 3 blocks of code to a single file of just over 430 lines. Skim-read the comment blocks before purging them all (to prove a point). Now have 210 lines (close to one half as much) to read and review.

Comments are always recommended when they explain why code is written as it is. These help the reader understand the considerations and approaches the coder has taken. Comments expressing "what" and "how" tend to clutter and distract, and these are too-often not maintained (creating uncertainty about why the code differs from its comment description). Trust that the reader will bring along the ability to read and understand well-written source code. After having only skimmed the entire source to get the concept of the approach taken, the four lines of comment above create_node() seem to be self-evident and redundant (for example.)

If you're not writing educational material for beginners, presume your readers are well-versed in the language syntax & semantics, and algorithms and data structures in general.

---

Heads up

typedef enum { false, true } bool;

Whether or not this single line needs to be in its own header file (and whether it will conflict with "reserved tokens" used by newer compilers) is worth considering.

DEFAULT_LENGTH_OF_CHILDREN_ARRAY could be CHILDREN_ARR_LEN
When the reader is zoomed-in to read & evaluate what?, how?, why? of source code, they are better able to hold-in-their-head simple and short tokens. Using overly elaborate token names like "deoxyribonucleic acid" instead of "DNA" suggests there may be overlooked references to "ribonucleic acid" ("RNA"), and the distinction from the other (that is NOT present) is important in the narrow, focussed context of the moment. In short: Get to the point! Even this Biology analogue demonstrates that information should be dense. (i.e.: tokens and variable names should be expressive, but brief(!), when/where possible.)

---

Design issues

It appears that each node will begin with 32 "empty" child pointers (to be assigned as needed when loading the dictionary's words), and a node's "offspring" array will double in size if/when required.

So, on a 64bit system, with its pointer size being 8bytes, each node (each letter) of "zoological" will require 32*8 (256) bytes of memory just for each of the word's 10 letters' child pointers. That's 2.5Kb to store one word. Consider "quickening". Again, 10 letters for one word. Of the 32 possible "children" of the first letter('q'), most dictionaries will only require the node's child 'u' be populated. In this case, that would be 31 unused pointers simply occupying memory.

Taking only the 26 lowercase letters of the English alphabet and a plain text dictionary file, a suggested project would be to tally, sort and examine how often each of the 26x26 letter pairs appear in those English words. After doing NO research, I'd be willing to speculate that there are a not-insignificant number of adjacent pairings that simply do not exist in a useful collection of English words.

In short: 32 may be an excessively large default allocation for every node.

---

parent->children = (Node **)realloc(parent->children, 2*parent->length_of_children_array*sizeof(Node *));

Doubling the number of child pointers may be problematic...
Consider a very simple case that starts with allocating only 1 node.
To double that, code asks to reallocate to now have 2 nodes.
To double that, code asks to reallocate to now have 4 nodes.
To double that, code asks to reallocate to now have 8 nodes.
Notice that the all the released nodes (that have been pooled-together again) can not be re-used for this growing progression? This goes on and on.
Suggested remedy: start with a reasonable generic guesstimate of requirements (8?) and grow the array (when needed) in smaller constant increments (4?)

---

The data structure will be populated as words are loaded from a (sorted) dictionary. This is likely to be suboptimal. Again, after completing NO research, minimally I'd speculate that, given any letter, the chances are greater that the next letter will be a vowel than a consonant. A linear search through the array of a node's "child letters" will not be efficient.

Suggestion: Add a counter to each node. While traversing the tree to install another word, increment that counter as the node is traversed. Use simple "swapping" to migrate the most frequently accessed nodes to the front of the child lists. Costly, but... This may pay off if spell-checking a massive document!

---

Loading an entire dictionary, with all these heap allocations required, in order to spell check a one page document will be disproportionately expensive!

---

Exploiting C's features

Here's a before and after (registering a new word) to consider:

    if (matching_child_found)
        current_node->is_end_of_word = true;
    else {
        Node *new_node;
        for (; word[i] != '\0'; i++) {
            new_node = create_node(word[i]);
            add_child(current_node, new_node);
            current_node = new_node;
        }
        current_node->is_end_of_word = true;
    }

... and ...

    if (!matching_child_found)
        for (; word[i]; i++)
            current_node = add_child(current_node, create_node(word[i]));
    current_node->is_end_of_word = true;

The function add_child() would need to be lightly modified to return the correct node pointer, of course.

Loading a dictionary's contents like this defines the objective. Is it worth optimising the process?

---

Final words

Congratulations to the OP for joining the fold and beginning to use the best programming language ever conceived! May you enjoy your adventures!

What you've implemented is called a 'trie' data structure. Of course, Python already has a plug-and-play module that does everything for the coder (in its own mysterious way).

Welcome to C where interested and curious coders come to explore and understand algorithms (rather than simply clipping together factory-ready Lego blocks).

Here's the Wikipedia page that may provide you with ideas about how to speed-up your version while shrinking its memory requirements.

Enjoy yourself!