Trie in Data Structures

Amit Kumar Ghosh 61 min read

17 Jun 2023

Advanced

333 Views

Introduction

Are you looking for a way to structure your data so that it can be processed more efficiently? Introducing the trie data structure, an incredibly versatile and powerful tool used to organize large amounts of information quickly. Also known as digital search trees, tries are a type of tree-based algorithm specifically designed for traversing and searching elements. It offers efficient access to data while keeping memory usage low, making it attractive for applications such as dictionary lookup or autocomplete functions. Read on this article to find out more about the exciting world of trie structures!

What is Trie Data Structure

The trie data structure has become an essential tool in computer science and information retrieval. It provides a way to efficiently store and search large sets of strings or sequences of data. The trie structure is similar to a tree, but with edges labeled by characters rather than containing nodes. Each node corresponds to a prefix of one or more strings. Compared to other data structures, the trie allows for quick look-ups and insertion of new entries, making it ideal for use in applications like autocomplete and spell-checking. By breaking down words into individual characters, the trie can accurately match user queries, ultimately enhancing the user experience with lightning-fast search results.

Structure of Trie node

In computer science, a Trie (also known as a prefix tree) is a tree-like data structure used for the efficient retrieval of strings or words. Each node in a Trie represents a character in a string, and the edges represent the links between characters. The structure of a Trie node typically contains the following components:

Value/Character: It holds the character associated with the node. Each node represents a single character in a string.
Children: It is an array or a map that stores references to child nodes. Each element in the array or map represents a possible character that can follow the current node.
Flag/End-of-Word Marker: It is a boolean flag that indicates whether the current node represents the end of a word. It is usually used to differentiate between complete words and prefixes.


 # Python code

 class TrieNode:
 
  # Trie node class
  def __init__(self):
   self.children = [None for _ in range(26)]
 
   # isEndOfWord is True if node represent the end of the word
   self.isEndOfWord = False


 // Trie node
 class TrieNode
 {
  TrieNode[] children = new TrieNode[ALPHABET_SIZE];
  // isEndOfWord is true if the node
  // represents end of a word
  boolean isEndOfWord;
 }


 // Trie node
 struct TrieNode
 {
   struct TrieNode *children[ALPHABET_SIZE];
   // isEndOfWord is true if the node
   // represents end of a word
   bool isEndOfWord;
 };

Basic Operations of Trie

Trie insertion

To insert a string into a Trie, you start at the root node and traverse down the tree, following the path determined by the characters of the string. If a node for a character does not exist, you create a new node. After inserting the last character of the string, you mark the node as the end of a word to indicate that a complete string has been inserted.

Process of insertion in trie

Start at the root of the Trie.
Initialize a variable currentNode to point to the root.
For each character in the string to be inserted, do the following:
Check if the current character is already a child of currentNode. If yes, update currentNode to the child node corresponding to the current character.
If the current character is not a child of currentNode, create a new TrieNode for the character and add it as a child of currentNode.
Update currentNode to the newly created child node.
After inserting all the characters, mark the last node as the end of a word (e.g., by setting a flag or attribute).
The insertion is complete.


 class TrieNode:
    def __init__(self):
        self.children = {}
        self.isEndOfWord = False


def createNode():
    return TrieNode()


def insert(root, word):
    currentNode = root

    for c in word:
        if c not in currentNode.children:
            currentNode.children[c] = createNode()
        currentNode = currentNode.children[c]

    currentNode.isEndOfWord = True


# Test the Trie implementation
if __name__ == "__main__":
    root = createNode()

    # Insert words into the Trie
    insert(root, "apple")
    insert(root, "banana")
    insert(root, "car")
    insert(root, "cat")
    insert(root, "dog")

    print("Trie insertion completed.")


 import java.util.HashMap;
 import java.util.Map;
 
 class TrieNode {
     Map<Character, TrieNode> children;
     boolean isEndOfWord;
 
     TrieNode() {
         children = new HashMap<>();
         isEndOfWord = false;
     }
 }
 
 class Trie {
     private TrieNode root;
 
     Trie() {
         root = new TrieNode();
     }
 
     void insert(String word) {
         TrieNode currentNode = root;
 
         for (char c : word.toCharArray()) {
             currentNode.children.putIfAbsent(c, new TrieNode());
             currentNode = currentNode.children.get(c);
         }
 
         currentNode.isEndOfWord = true;
     }
 }
 
 public class Main {
     public static void main(String[] args) {
         Trie trie = new Trie();
 
         // Insert words into the Trie
         trie.insert("apple");
         trie.insert("banana");
         trie.insert("car");
         trie.insert("cat");
         trie.insert("dog");
 
         System.out.println("Trie insertion completed.");
     }
 }


 #include <iostream>
 #include <unordered_map>
 
 using namespace std;
 
 // Trie Node
 struct TrieNode {
     unordered_map<char, TrieNode*> children;
     bool isEndOfWord;
 };
 
 // Create a new Trie Node
 TrieNode* createNode() {
     TrieNode* newNode = new TrieNode;
     newNode->isEndOfWord = false;
     return newNode;
 }
 
 // Insert a word into the Trie
 void insert(TrieNode* root, const string& word) {
     TrieNode* currentNode = root;
 
     for (char c : word) {
         if (currentNode->children.find(c) == currentNode->children.end()) {
             currentNode->children[c] = createNode();
         }
         currentNode = currentNode->children[c];
     }
 
     currentNode->isEndOfWord = true;
 }
 
 // Test the Trie implementation
 int main() {
     TrieNode* root = createNode();
 
     // Insert words into the Trie
     insert(root, "apple");
     insert(root, "banana");
     insert(root, "car");
     insert(root, "cat");
     insert(root, "dog");
 
     cout << "Trie insertion completed." << endl;
 
     return 0;
 }

Output

 Trie insertion completed.

Search in Trie

Searching for a string in a Trie involves traversing the tree based on the characters of the string. Starting at the root node, you follow the path determined by each character of the string. If at any point a node does not exist or the path ends before reaching the last character of the string, it means that the string does not exist in the Trie. However, if you successfully reach the last character and the node is marked as the end of a word, then the string is present in the Trie.

Process of search in trie

Start at the root node of the Trie.
Take the first character of the input string to be searched.
Check if there is a child node in the current node corresponding to the first character.
If there is a child node, move to that child node and proceed to the next character.
If there is no child node, the search string does not exist in the Trie. Return false or an appropriate result.
Repeat step 3 for each subsequent character in the input string.
After traversing all characters of the input string, check if the current node represents the end of a word.
If it does, the search string is found in the Trie. Return true or an appropriate result.
If it doesn't, the search string is a prefix of another word in the Trie, but not a complete word. Return false or an appropriate result.


 class TrieNode:
     def __init__(self):
         self.children = {}
         self.isWord = False
 
 class Trie:
     def __init__(self):
         self.root = TrieNode()
 
     def insert(self, word):
         node = self.root
         for ch in word:
             if ch not in node.children:
                 node.children[ch] = TrieNode()
             node = node.children[ch]
         node.isWord = True
 
     def search(self, word):
         node = self.root
         for ch in word:
             if ch not in node.children:
                 return False
             node = node.children[ch]
         return node.isWord
 
 
 trie = Trie()
 trie.insert("apple")
 trie.insert("banana")
 trie.insert("orange")
 trie.insert("pear")
 
 print("Search results:")
 print("apple:", "Found" if trie.search("apple") else "Not found")
 print("banana:", "Found" if trie.search("banana") else "Not found")
 print("orange:", "Found" if trie.search("orange") else "Not found")
 print("pear:", "Found" if trie.search("pear") else "Not found")
 print("grape:", "Found" if trie.search("grape") else "Not found")


 import java.util.HashMap;
 import java.util.Map;
 
 class TrieNode {
     Map<Character, TrieNode> children;
     boolean isWord;
 
     TrieNode() {
         children = new HashMap<>();
         isWord = false;
     }
 }
 
 class Trie {
     private TrieNode root;
 
     Trie() {
         root = new TrieNode();
     }
 
     void insert(String word) {
         TrieNode node = root;
         for (char ch : word.toCharArray()) {
             if (!node.children.containsKey(ch)) {
                 node.children.put(ch, new TrieNode());
             }
             node = node.children.get(ch);
         }
         node.isWord = true;
     }
 
     boolean search(String word) {
         TrieNode node = root;
         for (char ch : word.toCharArray()) {
             if (!node.children.containsKey(ch)) {
                 return false;
             }
             node = node.children.get(ch);
         }
         return node.isWord;
     }
 }
 
 public class Main {
     public static void main(String[] args) {
         Trie trie = new Trie();
         trie.insert("apple");
         trie.insert("banana");
         trie.insert("orange");
         trie.insert("pear");
 
         System.out.println("Search results:");
         System.out.println("apple: " + (trie.search("apple") ? "Found" : "Not found"));
         System.out.println("banana: " + (trie.search("banana") ? "Found" : "Not found"));
         System.out.println("orange: " + (trie.search("orange") ? "Found" : "Not found"));
         System.out.println("pear: " + (trie.search("pear") ? "Found" : "Not found"));
         System.out.println("grape: " + (trie.search("grape") ? "Found" : "Not found"));
     }
 }


 #include <iostream>
 #include <unordered_map>
 using namespace std;
 
 class TrieNode {
 public:
     unordered_map<char, TrieNode*> children;
     bool isWord;
 
     TrieNode() {
         isWord = false;
     }
 };
 
 class Trie {
 private:
     TrieNode* root;
 
 public:
     Trie() {
         root = new TrieNode();
     }
 
     void insert(const string& word) {
         TrieNode* node = root;
         for (char ch : word) {
             if (node->children.find(ch) == node->children.end()) {
                 node->children[ch] = new TrieNode();
             }
             node = node->children[ch];
         }
         node->isWord = true;
     }
 
     bool search(const string& word) {
         TrieNode* node = root;
         for (char ch : word) {
             if (node->children.find(ch) == node->children.end()) {
                 return false;
             }
             node = node->children[ch];
         }
         return node->isWord;
     }
 };
 
 int main() {
     Trie trie;
     trie.insert("apple");
     trie.insert("banana");
     trie.insert("orange");
     trie.insert("pear");
 
     cout << "Search results:" << endl;
     cout << "apple: " << (trie.search("apple") ? "Found" : "Not found") << endl;
     cout << "banana: " << (trie.search("banana") ? "Found" : "Not found") << endl;
     cout << "orange: " << (trie.search("orange") ? "Found" : "Not found") << endl;
     cout << "pear: " << (trie.search("pear") ? "Found" : "Not found") << endl;
     cout << "grape: " << (trie.search("grape") ? "Found" : "Not found") << endl;
 
     return 0;
 }

Output

 Search results:
apple: Found
banana: Found
orange: Found
pear: Found
grape: Not found

Delete from Trie

Deleting a string from a Trie involves recursively traversing the Trie to find the node corresponding to the last character of the string. Once found, you remove the end-of-word marker from the node to indicate that the string no longer exists in the Trie. If the node has no other children or descendants, you can safely remove the node from the Trie. This deletion process may continue recursively until you reach a node that has other children or descendants.

Process of deletion in trie

Start at the root of the trie and initialize a pointer (current) to the root.
Traverse the trie character by character, following the path of the key being deleted.
If the current character is not present in the current node's children, the key does not exist in the trie. Return.
If the key still has characters left, move the current pointer to the child node corresponding to the current character and continue to the next character.
If the key has no more characters left, it means we have found the node corresponding to the key.
Mark the node as non-leaf (if it is a leaf node) to indicate that the key no longer exists in the trie.
If the node has no children, i.e., it does not have any other keys associated with it, recursively delete the node.
While deleting the node, move up the tree until you reach a node that has more than one child or is marked as a non-leaf node.
Delete the current node and remove the link from its parent to the current node.
If the node has children, do not delete it. Instead, mark it as non-leaf to indicate that it is no longer associated with the deleted key.


 class TrieNode:
    def __init__(self):
        self.children = {}
        self.isEndOfWord = False

def createNode():
    newNode = TrieNode()
    newNode.isEndOfWord = False
    return newNode

def insert(root, word):
    current = root
    for c in word:
        if c not in current.children:
            current.children[c] = createNode()
        current = current.children[c]
    current.isEndOfWord = True

def isEmpty(root):
    return len(root.children) == 0

def remove(root, word, depth=0):
    if root is None:
        return None

    if depth == len(word):
        if root.isEndOfWord:
            root.isEndOfWord = False

            if isEmpty(root):
                del root
                root = None
        return root

    currentChar = word[depth]
    root.children[currentChar] = remove(root.children[currentChar], word, depth + 1)

    if isEmpty(root) and not root.isEndOfWord:
        del root
        root = None

    return root

def printTrie(root, prefix):
    if root.isEndOfWord:
        print(prefix)

    for c, child in root.children.items():
        prefix += c
        printTrie(child, prefix)
        prefix = prefix[:-1]

if __name__ == '__main__':
    root = createNode()

    insert(root, "apple")
    insert(root, "app")
    insert(root, "application")
    insert(root, "approve")
    insert(root, "bear")

    print("Trie before deletion:")
    prefix = ""
    printTrie(root, prefix)

    print("Deleting 'app' from Trie...")
    root = remove(root, "app")

    print("Trie after deletion:")
    prefix = ""
    printTrie(root, prefix)


 import java.util.HashMap;
 import java.util.Map;
 
 class TrieNode {
     Map<Character, TrieNode> children;
     boolean isEndOfWord;
 
     TrieNode() {
         children = new HashMap<>();
         isEndOfWord = false;
     }
 }
 
 public class Trie {
     private TrieNode root;
 
     Trie() {
         root = new TrieNode();
     }
 
     private void insert(String word) {
         TrieNode current = root;
         for (char c : word.toCharArray()) {
             current.children.putIfAbsent(c, new TrieNode());
             current = current.children.get(c);
         }
         current.isEndOfWord = true;
     }
 
     private boolean isEmpty(TrieNode node) {
         return node.children.isEmpty();
     }
 
     private TrieNode remove(TrieNode current, String word, int depth) {
         if (current == null) {
             return null;
         }
 
         if (depth == word.length()) {
             if (current.isEndOfWord) {
                 current.isEndOfWord = false;
 
                 if (isEmpty(current)) {
                     current = null;
                 }
             }
             return current;
         }
 
         char currentChar = word.charAt(depth);
         current.children.put(currentChar, remove(current.children.get(currentChar), word, depth + 1));
 
         if (isEmpty(current) && !current.isEndOfWord) {
             current = null;
         }
 
         return current;
     }
 
     private void printTrie(TrieNode node, StringBuilder prefix) {
         if (node.isEndOfWord) {
             System.out.println(prefix.toString());
         }
 
         for (Map.Entry<Character, TrieNode> entry : node.children.entrySet()) {
             prefix.append(entry.getKey());
             printTrie(entry.getValue(), prefix);
             prefix.deleteCharAt(prefix.length() - 1);
         }
     }
 
     public static void main(String[] args) {
         Trie trie = new Trie();
 
         trie.insert("apple");
         trie.insert("app");
         trie.insert("application");
         trie.insert("approve");
         trie.insert("bear");
 
         System.out.println("Trie before deletion:");
         StringBuilder prefix = new StringBuilder();
         trie.printTrie(trie.root, prefix);
 
         System.out.println("Deleting 'app' from Trie...");
         trie.remove(trie.root, "app", 0);
 
         System.out.println("Trie after deletion:");
         prefix.setLength(0);
         trie.printTrie(trie.root, prefix);
     }
 }


 #include <iostream>
 #include <unordered_map>
 using namespace std;
 
 struct TrieNode {
     unordered_map<char, TrieNode*> children;
     bool isEndOfWord;
 };
 
 TrieNode* createNode() {
     TrieNode* newNode = new TrieNode;
     newNode->isEndOfWord = false;
     return newNode;
 }
 
 void insert(TrieNode* root, const string& word) {
     TrieNode* current = root;
     for (char c : word) {
         if (current->children.find(c) == current->children.end()) {
             current->children[c] = createNode();
         }
         current = current->children[c];
     }
     current->isEndOfWord = true;
 }
 
 bool isEmpty(TrieNode* root) {
     for (auto& pair : root->children) {
         if (pair.second) {
             return false;
         }
     }
     return true;
 }
 
 TrieNode* remove(TrieNode* root, const string& word, int depth = 0) {
     if (root == nullptr) {
         return nullptr;
     }
 
     if (depth == word.length()) {
         if (root->isEndOfWord) {
             root->isEndOfWord = false;
 
             if (isEmpty(root)) {
                 delete (root);
                 root = nullptr;
             }
         }
         return root;
     }
 
     char currentChar = word[depth];
     root->children[currentChar] = remove(root->children[currentChar], word, depth + 1);
 
     if (isEmpty(root) && !root->isEndOfWord) {
         delete (root);
         root = nullptr;
     }
 
     return root;
 }
 
 void printTrie(TrieNode* root, string& prefix) {
     if (root->isEndOfWord) {
         cout << prefix << endl;
     }
 
     for (auto& pair : root->children) {
         prefix.push_back(pair.first);
         printTrie(pair.second, prefix);
         prefix.pop_back();
     }
 }
 
 int main() {
     TrieNode* root = createNode();
 
     insert(root, "apple");
     insert(root, "app");
     insert(root, "application");
     insert(root, "approve");
     insert(root, "bear");
 
     cout << "Trie before deletion:" << endl;
     string prefix;
     printTrie(root, prefix);
 
     cout << "Deleting 'app' from Trie..." << endl;
     root = remove(root, "app");
 
     cout << "Trie after deletion:" << endl;
     prefix = "";
     printTrie(root, prefix);
 
     return 0;
 }

Output

 Trie before deletion:
application
apple
approve
app
bear

Deleting 'app' from Trie...

Trie after deletion:
application
apple
approve
bear

Advantages of tries

Fast retrieval: Tries excel in retrieving values associated with keys that are strings or sequences. They provide a fast lookup time, typically O(L), where L is the length of the key being searched. This makes tries highly efficient when dealing with large datasets.
Prefix search: Tries are specifically designed for prefix-based searching. They allow you to find all keys that have a common prefix, making them useful in autocomplete features, dictionary implementations, and searching for words with similar beginnings.
Space efficiency: While tries require more memory than other data structures like hash tables or arrays, they are generally more space-efficient than those structures when storing a large number of keys with common prefixes. Tries avoid duplicating common prefixes, leading to reduced memory usage.
Efficient insertion and deletion: Tries offer efficient insertion and deletion operations, often with a time complexity of O(L), where L is the length of the key being inserted or deleted. This makes tries suitable for dynamic data sets that require frequent updates.
Ordered traversal: Tries maintain the lexicographic order of keys, allowing for easy traversal in alphabetical or numerical order. This property can be leveraged for tasks such as generating sorted lists of keys or finding the closest matches to a given prefix.
Support for string operations: Tries can efficiently support various string operations, such as finding the longest common prefix, counting the occurrences of a particular prefix, or finding the kth smallest or largest string in the trie.
Compressed trie variants: Tries can be further optimized using compression techniques like ternary search tries (TSTs), radix tries, or Patricia tries. These variants reduce the memory overhead by compressing common prefixes, resulting in improved space efficiency.
Suitable for non-string data: While tries are primarily associated with strings, they can also be adapted to handle other types of data. By assigning unique keys to non-string objects, tries can be used for efficient retrieval and storage of other structured data, such as IP addresses, XML tags, or file paths

Disadvantages of tries

Space Complexity: Tries can consume a significant amount of memory compared to other data structures. Each node in the trie contains a fixed number of pointers equal to the size of the alphabet, which can result in a large number of nodes and substantial memory overhead. This can be especially problematic when dealing with large dictionaries or datasets.
Memory Overhead: Along with the space complexity, tries also have a high memory overhead per node. Each node typically requires additional memory to store character labels or pointers, which can be inefficient for languages with large character sets or when dealing with long strings.
Insertion and Deletion Performance: While searching in tries is generally efficient with a time complexity of O(m), where m is the length of the key being searched, insertion and deletion operations can be relatively costly. This is because modifications to the trie structure, such as adding or removing nodes, may require rearranging the tree and updating multiple pointers, leading to increased time complexity.
Lack of Flexibility: Tries are primarily designed for storing and searching for strings or sequences of characters. They are less suitable for handling other types of data, such as numerical values or complex data structures. Tries do not naturally support operations like range queries or partial matches, which can limit their applicability in certain scenarios.
Memory Fragmentation: As tries grow and shrink due to insertions and deletions, they can suffer from memory fragmentation. This fragmentation occurs when nodes are created and destroyed irregularly, leaving unused memory gaps between nodes. Over time, this can lead to inefficient memory utilization and potential performance degradation.
Complexity with Variable-Length Keys: Tries can become more complex to implement and use when dealing with variable-length keys. In such cases, extra care is required to handle keys of different lengths, and additional mechanisms, such as sentinel nodes or termination flags, may be needed to indicate the end of a key.

Application of trie data structure

Dictionary and spell checking: Tries are commonly used to implement dictionaries and spell checkers. The trie structure allows for quick and efficient lookup of words and helps in checking whether a given word is present in the dictionary or in suggesting possible correct spellings.
Autocomplete and text prediction: Tries are often used in applications that provide autocompletion or text prediction features. By traversing the trie based on the user's input, it becomes easy to suggest and complete words or phrases. This is widely used in search engines, text editors, and messaging applications.
IP routing and network routing tables: Tries are utilized in network routers to store and efficiently search routing information. Each node in the trie represents a portion of an IP address, enabling quick lookup and determination of the appropriate route for data packets.
Phone number and contact search: Tries are helpful for implementing phone books or contact lists where quick searching is required based on a phone number or a contact name. The trie structure allows for efficient retrieval of phone numbers or contacts based on partial matches or prefixes.
Huffman coding: Huffman coding is a compression algorithm that assigns variable-length codes to characters based on their frequency of occurrence. Tries are used in the construction of Huffman trees, where each character is stored as a leaf node, and the tree is traversed to encode or decode data efficiently.
Data compression and dictionary encoding: Tries can be employed in various data compression techniques, such as Lempel-Ziv-Welch (LZW) compression. Tries are used to build a dictionary of frequently occurring patterns or strings, which can be efficiently encoded and decoded during compression and decompression processes.
Auto-suggestions and search suggestions: Tries are utilized in search engines and applications that provide auto-suggestions or search suggestions as the user types. By traversing the trie based on the user's input, possible completions or search suggestions can be quickly generated and displayed.

Trie implementation


 # Python program for insert and search
 # operation in a Trie
 
 class TrieNode:
 
  # Trie node class
  def __init__(self):
   self.children = [None]*26
 
   # isEndOfWord is True if node represent the end of the word
   self.isEndOfWord = False
 
 class Trie:
 
  # Trie data structure class
  def __init__(self):
   self.root = self.getNode()
 
  def getNode(self):
 
   # Returns new trie node (initialized to NULLs)
   return TrieNode()
 
  def _charToIndex(self,ch):
 
   # private helper function
   # Converts key current character into index
   # use only 'a' through 'z' and lower case
 
   return ord(ch)-ord('a')
 
 
  def insert(self,key):
 
   # If not present, inserts key into trie
   # If the key is prefix of trie node,
   # just marks leaf node
   pCrawl = self.root
   length = len(key)
   for level in range(length):
    index = self._charToIndex(key[level])
 
    # if current character is not present
    if not pCrawl.children[index]:
     pCrawl.children[index] = self.getNode()
    pCrawl = pCrawl.children[index]
 
   # mark last node as leaf
   pCrawl.isEndOfWord = True
 
  def search(self, key):
 
   # Search key in the trie
   # Returns true if key presents
   # in trie, else false
   pCrawl = self.root
   length = len(key)
   for level in range(length):
    index = self._charToIndex(key[level])
    if not pCrawl.children[index]:
     return False
    pCrawl = pCrawl.children[index]
 
   return pCrawl.isEndOfWord
 
 # driver function
 def main():
 
  # Input keys (use only 'a' through 'z' and lower case)
  keys = ["the","a","there","anaswe","any",
    "by","their"]
  output = ["Not present in trie",
    "Present in trie"]
 
  # Trie object
  t = Trie()
 
  # Construct trie
  for key in keys:
   t.insert(key)
 
  # Search for different keys
  print("{} ---- {}".format("the",output[t.search("the")]))
  print("{} ---- {}".format("these",output[t.search("these")]))
  print("{} ---- {}".format("their",output[t.search("their")]))
  print("{} ---- {}".format("thaw",output[t.search("thaw")]))
 
 if __name__ == '__main__':
  main()


 // Java implementation of search and insert operations
// on Trie
public class Trie {
 
 // Alphabet size (# of symbols)
 static final int ALPHABET_SIZE = 26;
 
 // trie node
 static class TrieNode
 {
  TrieNode[] children = new TrieNode[ALPHABET_SIZE];
 
  // isEndOfWord is true if the node represents
  // end of a word
  boolean isEndOfWord;
 
  TrieNode(){
   isEndOfWord = false;
   for (int i = 0; i < ALPHABET_SIZE; i++)
    children[i] = null;
  }
 };
 
 static TrieNode root;
 
 // If not present, inserts key into trie
 // If the key is prefix of trie node,
 // just marks leaf node
 static void insert(String key)
 {
  int level;
  int length = key.length();
  int index;
 
  TrieNode pCrawl = root;
 
  for (level = 0; level < length; level++)
  {
   index = key.charAt(level) - 'a';
   if (pCrawl.children[index] == null)
    pCrawl.children[index] = new TrieNode();
 
   pCrawl = pCrawl.children[index];
  }
 
  // mark last node as leaf
  pCrawl.isEndOfWord = true;
 }
 
 // Returns true if key presents in trie, else false
 static boolean search(String key)
 {
  int level;
  int length = key.length();
  int index;
  TrieNode pCrawl = root;
 
  for (level = 0; level < length; level++)
  {
   index = key.charAt(level) - 'a';
 
   if (pCrawl.children[index] == null)
    return false;
 
   pCrawl = pCrawl.children[index];
  }
 
  return (pCrawl.isEndOfWord);
 }
 
 // Driver
 public static void main(String args[])
 {
  // Input keys (use only 'a' through 'z' and lower case)
  String keys[] = {"the", "a", "there", "answer", "any",
      "by", "bye", "their"};
 
  String output[] = {"Not present in trie", "Present in trie"};
 
 
  root = new TrieNode();
 
  // Construct trie
  int i;
  for (i = 0; i < keys.length ; i++)
   insert(keys[i]);
 
  // Search for different keys
  if(search("the") == true)
   System.out.println("the --- " + output[1]);
  else System.out.println("the --- " + output[0]);
 
  if(search("these") == true)
   System.out.println("these --- " + output[1]);
  else System.out.println("these --- " + output[0]);
 
  if(search("their") == true)
   System.out.println("their --- " + output[1]);
  else System.out.println("their --- " + output[0]);
 
  if(search("thaw") == true)
   System.out.println("thaw --- " + output[1]);
  else System.out.println("thaw --- " + output[0]);
 
 }
}


 // C++ implementation of search and insert
 // operations on Trie
 #include <bits/stdc++.h>
 using namespace std;
 
 const int ALPHABET_SIZE = 26;
 
 // trie node
 struct TrieNode
 {
  struct TrieNode *children[ALPHABET_SIZE];
 
  // isEndOfWord is true if the node represents
  // end of a word
  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;
 }
 
 // If not present, inserts key into trie
 // If the key is prefix of trie node, just
 // marks leaf node
 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];
  }
 
  // mark last node as leaf
  pCrawl->isEndOfWord = true;
 }
 
 // Returns true if key presents in trie, else
 // false
 bool search(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])
    return false;
 
   pCrawl = pCrawl->children[index];
  }
 
  return (pCrawl->isEndOfWord);
 }
 
 // Driver
 int main()
 {
  // Input keys (use only 'a' through 'z'
  // and lower case)
  string keys[] = {"the", "a", "there",
      "answer", "any", "by",
      "bye", "their" };
  int n = sizeof(keys)/sizeof(keys[0]);
 
  struct TrieNode *root = getNode();
 
  // Construct trie
  for (int i = 0; i < n; i++)
   insert(root, keys[i]);
 
  // Search for different keys
  char output[][32] = {"Not present in trie", "Present in trie"};
 
  // Search for different keys
  cout<<"the"<<" --- "<<output[search(root, "the")]<<endl;
  cout<<"these"<<" --- "<<output[search(root, "these")]<<endl;
  cout<<"their"<<" --- "<<output[search(root, "their")]<<endl;
  cout<<"thaw"<<" --- "<<output[search(root, "thaw")]<<endl;
  return 0;
 }

Output

 
 the --- Present in trie
these --- Not present in trie
their --- Present in trie
thaw --- Not present in trie

Summary

In conclusion, understanding the fundamentals of a trie data structure is key to efficiently working with larger datasets. By leveraging tries, you can drastically improve the performance of certain algorithms, making them much faster and better suited for larger datasets. Additionally, their ability to quickly store and retrieve specific data makes them an ideal tool for applications such as search engines and social media platforms. Now that you know the basics of this powerful tool, why not give it a try? Taking up the challenge of building your own trie structures or implementing existing ones into your projects can be incredibly rewarding and open up many new possibilities!