Get started with “Trie” data structure!

Have you ever thought how word autocomplete or spell checker works? How google identifies the correct search answer for the query that we have passed in seconds?

Suggesting “soft” keyword to auto complete my word and showing suggestions also similar to my word.

We have studied various data structures over the time like arrays, graph, trees, Linked List, etc. One such data structure that you may say derived using the concepts of all these data structures is “Trie”.

Trie is a N-ary tree data structure that is generally used to store and process strings. We declare Trie just like a tree node similar to nodes we studied in trees, difference here is each node stores alphabets or strings. Here, each node has several path, generally if we are taking the case of English Alphabets, than each node will have 26 paths (a -> z).
Let’s understand this by a niche representation of words like “abcd”, “abce”, “bcad”, “da”. For simplicity and easy explanation, I have taken small and initial alphabets word, to store other words we can extend our array size to store tille ‘z’.

Trie — “Basic Representation”

As, you can see here each node here stores some alphabet which you can also that each node is storing the prefix of our final string until the nodes came to end. That’s why Trie is also know as “Prefix Tree”.

There are two ways to represent or code a Trie data structure: Using arrays and hashmaps.
Here, I will be focusing more on implementing Trie using Array, and I believe if you able to understand array representation you can easily catch the concept behind the map implementation.

This is the code to Implement Trie (Prefix Tree), check it out yourself over given LeetCode problem link.

class TrieNode{
    public:
    bool word;
    TrieNode *children[26];
    TrieNode(){
        word = false;
        for(int i = 0; i<26; i++) children[i] = NULL;
    }
};

class Trie {
public:
    TrieNode* root;
    Trie() {
        root = new TrieNode();
    }
   
    void insert(string word) {
        int n = word.length();
        TrieNode* curr = root;
        for(int i = 0; i<n; i++){
            int k = word[i] - 'a';
            if(curr -> children[k] == NULL) curr -> children[k] = new TrieNode();
            curr = curr -> children[k];
        }
        curr -> word = true;
    }
    
    bool search(string word) {
        int n = word.length();
        TrieNode* curr = root;
        for(int i = 0; i<n; i++){
            int k = word[i] - 'a';
            if(curr -> children[k] == NULL) return false;
            curr = curr -> children[k];
        }
        return curr -> word;
    }
    
    bool startsWith(string prefix) {
        int n = prefix.length();
        TrieNode* curr = root;
        for(int i = 0; i<n; i++){
            int k = prefix[i] - 'a';
            if(curr -> children[k] == NULL) return false;
            curr = curr -> children[k];
        }
        return true;
    }
};

Let’s understand this code a bit, I’ll highly recommend to try drawing out this on your notebook for clarity:
1. In this code, we are performing three tasks: inserting, searching for the word, and searching for the prefix.
2. As evident, we have declared a TrieNode having array for storing TrieNode itself for english alphabets and boolean word to check if a word is complete or not.
3. We have created another class “Trie” to implement our methods insert, search, and prefix.
4. To insert a word, we are simply iterating over each alphabet node by node, if we found the node for that particular alphabet we are simply traversing to next node for next alphabet in the word, else after creating new node for that particular alphabet we are moving forward.
This statement might cross above your brains as for me when I first tried to understand this, but I can bet trie to visualize it using pen and paper.
5. The catch is to make sure our inserted word has ended or to keep a check on word end, we have taken that boolean word which will denote the end of that word. As, soon as we traverse through last node/ last alphabet we are making another NULL node, but here we will set the value of word to be set as “TRUE”, which will help us to find searching the word.
5. In a similar pattern, we are finding the prefix, as soon as we are getting the nodes for alphabets and value of children for that particular alphabet is not null, it means it is present in our trie. If we reach end of the prefix word without encountering any NULL node we are returning True.

Don’t worry if you didn’t got this at first read, try to code it and visualize how code is working and things are getting done. I assure you once you get the logic behind this, you can solve questions on this easily.

To visualize you better here I have represented how my code is working for these some words.

You guys can try out with some questions on LeetCode: https://leetcode.com/tag/trie

My favorite question on trie: https://leetcode.com/problems/maximum-xor-with-an-element-from-array/

Here’s my repository link if you want the solution of leetcode questions: https://github.com/Aadi71/Data-Structure-and-Algorithm-with-Aadi

I hope you liked my explanation, in case you have some query or doubt do reach me out or comment here.

Thanks for reading!
https://linktr.ee/aadijain7