Trie - C P P

• Space complexity for Insertion = O(n * m)

• Space Utilization is better
• Autocomplete/Spell Checker/Predictive Text
  • Finding all keys with a common prefix Trie is better as Hashmap will have to traverse everything

    const int ALPHABET_SIZE = 26;
    struct TrieNode {
         struct TrieNode *children[ALPHABET_SIZE];
         bool isEndOfWord;
    };
    // Returns new trie node (initialized to NULLs)
    struct TrieNode *getNode(void) {
        struct TrieNode *pNode =  new TrieNode;
        pNode->isEndOfWord = false;
        for (int i = 0; i < ALPHABET_SIZE; i++)
            pNode->children[i] = NULL;
        return pNode;
    }
    // Insert
    void insert(struct TrieNode *root, string key) {
        struct TrieNode *pCrawl = root;
        for (int i = 0; i < key.length(); i++)
        {
            int index = key[i] - 'a';
            if (!pCrawl->children[index])
                pCrawl->children[index] = getNode();
            pCrawl = pCrawl->children[index];
        }
        pCrawl->isEndOfWord = true;
    }