delete a key in a trie

Question

To delete a key from a trie, there are four cases:

For the explanation of trie data structure, please check the following link: http://www.geeksforgeeks.org/trie-insert-and-search/

(1) Key is not in the trie.

(2) Key present in the trie as a unique key.

(3) Key is the prefix of another longer key.

(4) Key presents in the trie, having at least one other key as prefix key.

The following code is my implementation of deleting a key from a trie.

struct trie_node
{
    int mark;
    struct trie_node* children[ALPHABET_SIZE];
};

struct trie
{
    struct trie_node* root;
    int count;  
};

// check if a trie node has no children
bool isFreeNode(struct trie_node* p)
{
    int i;
    for(i = 0; i < ALPHABET_SIZE; ++i)
    {
        if(p->children[i])
            return false;
    }
    return true;
}

bool isLeafNode(struct trie_node* p)
{
    return p->mark == 1;
}

bool deleteHelper(struct trie_node* root, char* key, int level, int len)
{
    int ind;
    //check if the key is in the trie.
    if(root!=NULL)
    {
        if(level==len)
        {
            //check if the key is in the trie.
            if(root->mark==1)
            {
                root->mark = 0;

                //Is it an unique key?
                            if(isFreeNode(root))
                {
                    return true;
                }
                return false;
            }               
        }
        else
        {
            ind = *(key+level) - 'a';
            if(deleteHelper(root->children[ind], key, level+1, len))
            {
                free(root->children[ind]);
                root->children[ind] = NULL;

                //check if the node is an unique key node. Case (2) and
                            //and case (4) can both generates unique key node. 
                            if(!isLeafNode(root) && isFreeNode(root))
                {
                    return true;
                }
                return false;
            }
        }
    }   
    return false;
}

void deleteKey(struct trie* trie, char* key)
{
    int len = strlen(key);
    if(len>0)
    {
        //check if the key is the only one in the trie
            if(deleteHelper(trie->root, key, 0, len))
        {
            free(trie->root);
        }
    }
}

Answer 1

1. Check your indentation, mostly for comments. While there are a lots of indent styles for C, none of them recommends removing the spaces after if and for.

2. Using recursive functions is not the idiomatic way of doing things in C, but that's OK.

3. It's generally better to check for error conditions before, and handle the general case afterwards. This is a good idea because the "error condition" is generally smaller. For example, if you check for root == NULL case first, the reader doesn't have to remember that there is possibly an else branch. This will also force you to make return false cases more explicit in your if/else branches. I think it's a good thing.

4. You can write if (root->mark) instead of if(root->mark==1).

5. This code is too long:

   // Is it an unique key?
   if (isFreeNode(root))
   {
       return true;
   }
   return false;
   

   Simple write return isFreeNode(root);. Same thing for (!isLeafNode(root) && isFreeNode(root))

6. *(key+level) should be written key[level].

7. You don't set trie->root to NULL after freeing it: this is not consistent with the earlier free().