Algotree > Algorithms > Trie

Trie

Trie or Prefix Tree / Radix Tree

The word trie is derived from the word ‘retrieval’.

TRIE key observations

The data in the trie is structured like a tree.
In the example, the trie is created with the capability of storing all english words containing small letters.
Each node in the trie stores an alphabet as well as a boolean flag. The flag indicates if the word ends with the stored alphabet. In the below example the red nodes mark the end of the word.
Words are retrieved by traversing from the root of the trie down the branch of the tree.

Trie

Time complexity of creating a TRIE : O(N*L) where ‘N’ words are to be inserted into the trie and the average length of each word is ‘L’.
Time complexity of searching in a TRIE : O(N*L) where ‘N’ words are to be searched in the trie and the average length of each word is ‘L’.

C++14 implementation of Trie insert, search and printing words in lexical order

#include<iostream>
using namespace std;

class TrieNode {

    public:
        TrieNode * children[26];
        bool end_of_word;
        char letter;
        TrieNode() {
            end_of_word = false;
            for (int i=0; i<26; i++) {
                children[i] = NULL;
            }
            letter = '\0';
        }
};

class Trie {

    public:

    TrieNode root;

    // Insert the word in the trie
    void Insert (string str) {
        TrieNode * current = &root;
        for (size_t i=0; i<str.size(); i++) {
            if (current->children[str.at(i)-'a'] == NULL) {
                current->children[str.at(i)-'a'] = new TrieNode;
                current->children[str.at(i)-'a']->letter = str.at(i);
            }
            current = current->children[str.at(i)-'a'];
        }
        current->end_of_word = true;
    }

    // Search the word in trie
    TrieNode * Search (string str) {
        TrieNode * current = &root;
        for (size_t i=0; i<str.size(); i++) {
            if (current->children[str.at(i)-'a']) {
                current = current->children[str.at(i)-'a'];
             } else {
                current = NULL;
                break;
             }
        }
        return current;
    }

    // Print the words with the specified prefix in lexical order
    void PrintLexical (TrieNode * current, string prefix, string suffix) {
        if (current->end_of_word and suffix.size() != 0) {
            cout << prefix+suffix << endl;
        }
        for (int i=0; i<26; i++) {
            string temp = suffix;
            if (current->children[i]) {
                temp += current->children[i]->letter;
                PrintLexical(current->children[i], prefix, temp);
            }
        }
    }
};

int main() {

    Trie T;

    // Insert word(s) in the trie
    T.Insert("we");
    T.Insert("walk");
    T.Insert("want");
    T.Insert("wish");
    T.Insert("wit");
    T.Insert("am");
    T.Insert("yo");
    T.Insert("will");
    T.Insert("wee");
    T.Insert("war");
    T.Insert("warp");
    T.Insert("win");

    // Search for the prefix in the trie
    string prefix("wa");

    TrieNode * current = T.Search(prefix);

    if (current == NULL or current == &T.root) {
        cout << "No words with matching prefix found" << endl;
    } else {
        // Prefix has been found in the tree, look for children
        bool haschildren = false;
        for (int c=0; c<26; c++) {
            if (current->children[c] != NULL) {
                 haschildren = true; break;
            }
        }
        // No words found with the prefix (only the prefix was found)
        if (haschildren == false) {
            cout << "No words with matching prefix found" << endl;
        } else {
            cout << "Word(s) with prefix: " << prefix << endl;
            T.PrintLexical(current, prefix, "");
        }
    }
    return 0;
}

Output

Word(s) with prefix: wa
walk
want
war
warp