Insert Unique element into trie

Question

void insert(struct node *root, string s)
{
    struct node *temp = root;
    for(int i=0;i<s.length();i++)
    {
        if(temp->idx[s[i]-'a']==NULL)
            temp->idx[s[i]-'a']=create();
        temp = temp->idx[s[i]-'a'];
        (temp->cnt)++;
    }
    temp->end=1;
}

So I am going to insert string to create a unique trie data structure, but this insert algortihm is not able to detect any duplicate string, can someone help me how this insert algorithm works only for inserting unique elements?

Answer 1

You can check for string duplicates using end property of struct node. Let's call find to this boolean method and add it as first line of insert method.

bool find(struct node *root, string s)
{
    struct node *temp = root;
    for(int i=0;i<s.length();i++)
    {
        if(temp->idx[s[i]-'a']==NULL)
            return false;
        temp = temp->idx[s[i]-'a'];
    }
    return temp->end;
}

void insert(struct node *root, string s)
{
    if(!find(root, s)) return;
    struct node *temp = root;
    for(int i=0;i<s.length();i++)
    {
        if(temp->idx[s[i]-'a']==NULL)
            temp->idx[s[i]-'a']=create();
        temp = temp->idx[s[i]-'a'];
        (temp->cnt)++;
    }
    temp->end=1;
}

Runtime: The same as before O(m) where m is length of s.

Note: I made find method since anyway you need to traverse at most twice that path of the trie. One way is the mentioned at the beginning, a second one is to check duplicates (end property) when you have the node that represent s and if it is indeed a duplicated string then you traverse again s path fixing the extra +1 in cnt property.