Introduction to Trie

What is a Trie ?

A trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

• Trie() Initializes the trie object.
• void insert(String word) Inserts the string word into the trie.
• boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
• boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

The above piece of information is taken from Leetcode

Now lets understand

reference image

Basically suppose we have two strings “apple” and “apps”. First lets process “apple”. Starting with have a reference node (containing *list[26] and a bool flag) we check if ‘a’ is null or not if it is then we create a reference trie for ‘a’ and move to that. Now we have ‘p’ then we again check is list[‘p’ — ‘a’] is null or not and if it is null then we create a reference node trie for p. We continue this until we reach the last character. We then set flag as true for the reference trie of last character denoting that we have reached the end of the trie.

For searching, suppose we want to check the string “app” then first we check if ‘a’ is present in the root node/ trie if yes we move to the reference trie of ‘a’ or else we simply return false. After that we check for ‘p’. Lastly after the query string is processed we check whether the flag is true or not, if true it means that we have reached the end and there exists the string else the string is not present.

For the third part i,e startsWith we follow the same procedure as searching but at last we see if we are on a not null trie it means that the prefix is present in the trie.

Below is the code. Please go through it and ask me any doubts in this( no matter how small they are :) )

struct Node{
    Node* links[26];
    bool flag = false;
    bool containsKey(char ch){
        return links[ch - 'a'] == NULL;
    }
    void put(char ch, Node* node){
        links[ch - 'a'] = node;
    }

    Node* get(char ch){
        return links[ch - 'a'];
    }
    void setEnd(){
        flag = true;
    }
    bool isEnd(){
        return flag;
    }

};

class Trie{
private:
    Node* root;
public:
    Trie(){
        root = new Node();
    }

    void insert(string word){
        Node* node = root;
        for(int i = 0; i < word.size(); i++){
            if(!node->containsKey(word[i])){
                node->put(word[i], new Node());
            }
            node = node->get(word[i]);
        }
        node->setEnd();
    }

    bool search(string word){
        Node *node = root;
        for(int i = 0;i < word.size(); i++){
            if (!node->containsKey(word[i])){
                return false;
            }
            node = node->get(word[i]);
        }
        return node->isEnd();
    }

    bool startsWith(string prefix){
        Node *node = root;
        for(int i = 0; i < prefix.size(); i++){
            if (!node->containsKey(prefix[i])){
                return false;
            }
            node = node->get(prefix[i]);
        }
        return true;
    }
};

Thank you