Introduction to Trie

What is Trie ?

A Trie, also known as a Prefix Tree, is a tree-like data structure used for efficiently storing and searching a set of strings. Each path from the root to a leaf node represents a complete word or string.

Problem Statement

We have an input array dictionary,that consists of strings. each represents a word, we have to store these strings using least space and time complexity and we can also search any string efficiently.

dictionary = ["hello","help","mom"] // insert dictionary
search("hell") -> return false // search the word "hell"
search("help") -> return true // search the word "help"

Note: Assume all letters in dictionary to be small

You can try this at:

• https://practice.geeksforgeeks.org/problems/trie-insert-and-search0651/1

Insert Operation(Visual Walkthrough)

Search Operation(Visual Walkthrough)

Basic Structure of Trie

// trie class 
class Trie{
  TrieNode root;// root node of trie
  // function to insert the string in trie
  void insert(String str){}
  // function to check is string present or not
  boolean search(String str){}
}

// trienode class 
class TrieNode{
  TrieNode[] children = new TrieNode[26];// assuming all characters are small otherwise replace 26 with 256
  boolean isEnd;// to check wheteher there is any string which ends at this node 
}
    

Implementation

Java

class Main{
    public static void main(String args[]){
        Trie trie = new Trie();
        // insert the dictionary
        String[] dictionary = {"hello","help","mom"};
        for(String word: dictionary)trie.insert(word);// insert all the word in trie
        // search for the word: hell
        System.out.println("is hell exist: "+trie.search("hell"));
        // search for the word: help
        System.out.println("is help exist: "+trie.search("help"));
    } 
}



// trie class 
class Trie{
  TrieNode root;// root node of trie
  // constructor
  Trie(){
    root = new TrieNode();
  }
  // function to insert the string in trie
  void insert(String str){
    TrieNode start = root;
    // loop through string
    for(int i=0;i<str.length();i++){
        char c = str.charAt(i);// character
        if(start.letters[c-'a']==null){
            // means character is missing so include it
            start.letters[c-'a'] = new TrieNode();
        }
        start = start.letters[c-'a'];// move to next node
    }
    start.isEnd = true;// we reach to the last node so mark it true
  }
  // function to check is string present or not
  boolean search(String str){
    TrieNode start = root;
    // loop through string
    for(int i=0;i<str.length();i++){
        char c = str.charAt(i);// character
        if(start.letters[c-'a']==null)return false;
        start = start.letters[c-'a'];// move to next node
    }
    return start.isEnd;
  }
}

// trienode class 
class TrieNode{
  TrieNode[] letters = new TrieNode[26];// assuming all characters are small otherwise replace 26 with 256
  boolean isEnd;// to check wheteher there is any string which ends at this node 
  // constructor
  TrieNode(){
    for(int i=0;i<26;i++)letters[i] = null;
    isEnd = false;
  }
}
    

CPP

#include <iostream>
using namespace std;

class TrieNode {
public:
    TrieNode* letters[26];
    bool isEnd;

    TrieNode() {
        for (int i = 0; i < 26; i++)
            letters[i] = nullptr;
        isEnd = false;
    }
};

class Trie {
private:
  TrieNode* root;

public:
    Trie() {
      root = new TrieNode();
    }

    void insert(string str) {
        TrieNode* start = root;
        for (int i = 0; i < str.length(); i++) {
            char c = str[i];
            if (start->letters[c - 'a'] == nullptr) {
                start->letters[c - 'a'] = new TrieNode();
            }
            start = start->letters[c - 'a'];
        }
        start->isEnd = true;
    }

    bool search(string str) {
        TrieNode* start = root;
        for (int i = 0; i < str.length(); i++) {
            char c = str[i];
            if (start->letters[c - 'a'] == nullptr)
                return false;
            start = start->letters[c - 'a'];
        }
        return start->isEnd;
    }
};

int main() {
    Trie trie;
    string dictionary[] = { "hello", "help", "mom" };
    for (const string& word : dictionary)
      trie.insert(word);
   cout << "Is 'hell' present: " << (trie.search("hell") ? "true" : "false") << endl;
   cout << "Is 'help' present: " << (trie.search("help") ? "true" : "false") << endl;
    return 0;
}

Python

class TrieNode:
    def __init__(self):
        self.letters = [None] * 26
        self.isEnd = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, string):
        start = self.root
        for char in string:
            index = ord(char) - ord('a')
            if start.letters[index] is None:
                start.letters[index] = TrieNode()
            start = start.letters[index]
        start.isEnd = True

    def search(self, string):
        start = self.root
        for char in string:
            index = ord(char) - ord('a')
            if start.letters[index] is None:
                return False
            start = start.letters[index]
        return start.isEnd

trie = Trie()
dictionary = ["hello", "help", "mom"]
for word in dictionary:
    trie.insert(word)

print("Is 'hell' present:", trie.search("hell"))
print("Is 'help' present:", trie.search("help"))

Time complexity for inserting all words

O(N*L) where N is length of the dictionary and L is average length of words

Time complexity for searching a word

O(L) where L is average length of words