Trie Data Structure | Implementation in C++

A Trie, also known as a prefix tree, is a tree-like data structure that is used to store an associative array where the keys are sequences (usually strings). Tries are an efficient data structure for searching and manipulating large datasets that are made up of sequences, such as words in a dictionary or DNA sequences in genetics.

One of the main advantages of using a Trie is its ability to search for patterns within a dataset. For example, if you wanted to search for all words in a dictionary that start with the prefix "pre," you could use a Trie to quickly find those words. This is because a Trie stores data in a way that allows for fast prefix searching.

To understand how a Trie works, let's take a look at an example. Imagine we have a Trie that stores the words "hello," "help," and "held." The Trie would look something like this:

      h
     / \
    e   he
   /   /  \
  l   lp   ld
 /   /
l   e

As you can see, each node in the Trie represents a letter in one of the words. The path from the root of the Trie to a leaf node represents a complete word. In this example, the path "h-e-l-p" represents the word "help."

Inserting a new word into a Trie is a simple process. First, we start at the root node and compare the first letter of the word to the letters stored at each child node. If we find a match, we move down to the next level of the Trie and continue the process until we reach the end of the word. If we don't find a match, we simply add a new child node for the missing letter.

For example, let's say we want to insert the word "helmet" into the Trie above. The process would look like this:

1. Start at the root node (h).
2. Move to the child node with the letter "e" (e).
3. Move to the child node with the letter "l" (l).
4. There is no child node with the letter "m," so we add a new child node (m).
5. There is no child node with the letter "e," so we add a new child node (e).
6. There is no child node with the letter "t," so we add a new child node (t).

The resulting Trie would look like this:

      h
     / \
    e   he
   /   /  \
  l   lp   ld
 /   /      \
l   e        t
              \
               m
              /
             e

Searching for a word in a Trie is similar to inserting a word. We start at the root node and follow the path through the Trie, comparing each letter to the letters stored at the child nodes. If we reach a leaf node and the word is complete, we know the word is in the Trie. If we reach a leaf node and the word is not complete, or if we reach a point where there are no more child nodes to follow, we know the word is not in the Trie.

Implementation of Trie in C++

Here is an example of a C++ implementation of a Trie data structure:

#include <iostream>
#include <unordered_map>

using namespace std;

const int ALPHABET_SIZE = 26;

struct TrieNode {
  bool isEndOfWord;
  unordered_map<char, TrieNode*> children;
};

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

  void insert(string s) {
    TrieNode* current = root;
    for (char c : s) {
      if (current->children.count(c) == 0) {
        current->children[c] = new TrieNode();
      }
      current = current->children[c];
    }
    current->isEndOfWord = true;
  }

  bool search(string s) {
    TrieNode* current = root;
    for (char c : s) {
      if (current->children.count(c) == 0) {
        return false;
      }
      current = current->children[c];
    }
    return current->isEndOfWord;
  }

 private:
  TrieNode* root;
};

int main() {
  Trie trie;
  trie.insert("hello");
  trie.insert("world");
  cout << trie.search("hello") << endl;  // prints 1
  cout << trie.search("world") << endl;  // prints 1
  cout << trie.search("hell") << endl;   // prints 0
  cout << trie.search("worl") << endl;   // prints 0
  return 0;
}

This Trie implementation uses an unordered_map to store the children nodes of each TrieNode. The insert function adds a new string to the Trie by iterating over each character in the string and adding it to the Trie, one character at a time. The search function searches for a string in the Trie by following the path through the tree, one character at a time, until it reaches the end of the string. If the string is present in the Trie, the search function returns true, otherwise it returns false.