Finding words in tree by prefix

Question

In my binary search tree I want to create a function that can get all words starting with a prefix and store all words in an array called results this is my tree

struct BinarySearchTree_t
{
    char *mot,*def;
    struct BinarySearchTree_t *left;
    struct BinarySearchTree_t *right;
};
typedef struct BinarySearchTree_t BinarySearchTree;

my function :

size_t findWordsByPrefix(BinarySearchTree* tree, char* prefix, char*** results)
{
    BinarySearchTree *tmp;
        tmp=tree;

    static int size=0;

    if (!tmp)
        return 0;
    else if (strncmp(tmp->mot,prefix,strlen(prefix))==0)
    {

        (*results)= realloc(*results,(1+size)*sizeof(*(*results)));
        (*(*results+size))= malloc(strlen(tmp->mot)*sizeof(char));
        strcpy((*results)[size],tmp->mot);
        size++;
       return (1 + findWordsByPrefix(tmp->left,prefix, &results) + findWordsByPrefix(tmp->right,prefix, &results));
    }
    else
        return (strncmp(tmp->mot,prefix,strlen(prefix))<0)?findWordsByPrefix(tmp->right,prefix, &results):findWordsByPrefix(tmp->left,prefix, &results) ;
}

This function should return a number of words starting with the given prefix. my problem is that the program crash when it is run , and I don't how to resize my array results so every time I found a word I should increase the size of the results array .

and I would know how exacly manipulate the pointer of pointer of pointer given in arg of this function (char ***results) : what exactly means?

Answer 1

If I simply compile your code, I get severe compiler warnings including:

1>binarysearchtree.c(98) : warning C4047: 'function' : 'char ***' differs in levels of indirection from 'char ****'
1>binarysearchtree.c(98) : warning C4024: 'findWordsByPrefix' : different types for formal and actual parameter 3

This alone will cause a crash -- you are calling your own function recursively with the wrong arguments.

Next, I believe you need to allocate one more than the length of the string, to hold a copy of a string:

malloc((strlen(tmp->mot) + 1 )*sizeof(char))

Next, you're passing around an array of strings of variable size -- and storing the size in a static variable. It's impossible to know if this will work, so don't do it.

Instead, if you want to use a dynamic array of strings, I suggest extracting out a struct to hold them, like so:

struct ResultTable_t
{
    int    size;
    char **results;
};

typedef struct ResultTable_t ResultTable;

void InitializeResults(ResultTable *p_table)
{
    p_table->size = 0;
    p_table->results = NULL;
}

void AddResult(ResultTable *p_table, char *result)
{
    if (result == NULL)
        return;
    p_table->size++;
    p_table->results = realloc(p_table->results, p_table->size * sizeof(*p_table->results));
    p_table->results[p_table->size-1] = malloc((strlen(result) + 1) * sizeof(**p_table->results));
    strcpy(p_table->results[p_table->size-1], result);
}

void FreeResults(ResultTable *p_table)
{
    if (p_table->results != NULL)
    {
        int i;

        for (i = 0; i < p_table->size; i++)
        {
            free(p_table->results[i]);
        }
        free(p_table->results);
    }
    p_table->size = 0;
    p_table->results = NULL;
}

(As an improvement, you might consider using geometric growth instead of linear growth for your table of results.)

Then your function becomes:

size_t findWordsByPrefix(BinarySearchTree* tree, char* prefix, ResultTable *p_table)
{
    if (!tree)
        return 0;
    else if (strncmp(tree->mot,prefix,strlen(prefix))==0)
    {
        AddResult(p_table, tree->mot);
        return (1 + findWordsByPrefix(tree->left,prefix, p_table) + findWordsByPrefix(tree->right,prefix, p_table));
    }
    else if (strncmp(tree->mot,prefix,strlen(prefix))<0)
    {
        return findWordsByPrefix(tree->right,prefix, p_table);
    }
    else
    {
        return findWordsByPrefix(tree->left,prefix, p_table);
    }
}

And you would use it like:

ResultTable results;

InitializeResults(&results);

// Get some prefix to search for.
char prefix = GetSomePrefix();

int size = findWordsByPrefix(tree, prefix, &results);

// Do something with the results

// Free all memory of the results

FreeResults(&results);

Update

If the ResultTable is distasteful for some reason, you can pass the dynamic array and array sizes in directly:

void AddResult(char ***p_results, int *p_size, char *word) 
{ 
    if (word == NULL) 
        return; 
    (*p_size)++; 
    (*p_results) = realloc(*p_results, ((*p_size)+1) * sizeof(**p_results)); 
    (*p_results)[(*p_size)-1] = malloc((strlen(word) + 1) * sizeof(***p_results)); 
    strcpy((*p_results)[(*p_size)-1], word);
}

void FreeResults(char ***p_results, int *p_size)
{
    int i;

    if (p_results == NULL || *p_results == NULL)
        return;

    for (i = 0; i < (*p_size); i++)
    {
        free ((*p_results)[i]);
    }
    free (*p_results);

    *p_results = NULL;
    *p_size = 0;
}

size_t findWordsByPrefix(BinarySearchTree* tree, char* prefix, char ***p_results, int *p_size)
{
    if (!tree)
        return 0;
    else if (strncmp(tree->mot,prefix,strlen(prefix))==0)
    {
        AddResult(p_results, p_size, tree->mot);
        return (1 + findWordsByPrefix(tree->left,prefix, p_results, p_size) + findWordsByPrefix(tree->right,prefix, p_results, p_size));
    }
    else if (strncmp(tree->mot,prefix,strlen(prefix))<0)
    {
        return findWordsByPrefix(tree->right,prefix, p_results, p_size);
    }
    else
    {
        return findWordsByPrefix(tree->left,prefix, p_results, p_size);
    }
}

and use like:

char **results = NULL;
int    tablesize = 0;

// Get some prefix to search for.
char prefix = GetSomePrefix();

int size = findWordsByPrefix(tree, prefix, &results, &tablesize);

// Do something with the results

// Free all memory of the results

FreeResults(&results, &tablesize);