🌱 Trie (Prefix Tree) – Complete In-Depth Explanation

A Trie (also known as a prefix tree) is a tree-like data structure that is used for efficient storage and retrieval of strings. It's particularly useful for searching, autocompletion, and spell checking.

📌 Why are Tries Important?

🚀 Efficient Prefix Searching: Fast retrieval of words with a common prefix.
💡 Autocompletion: Used in search engines and text editors.
✔️ Spell Checking: Identifying misspelled words.

📌 Understanding Tries with an Example

Let's say we want to store the words "cat", "car", "dog", "dot", and "cab" in a Trie. The Trie would look like this:

Each node in the Trie represents a character. Paths from the root to a node marked as an "end of word" represent a stored word.

🔹 Key Points

Nodes store characters.
Paths represent words.
Efficient for prefix-based searches.

🛠 Solution Approach

The basic operations on a Trie are:

📌 1. Insertion

To insert a word, we traverse the Trie, creating nodes as needed, until we reach the end of the word. We mark the last node as an "end of word".

📌 2. Search

To search for a word, we traverse the Trie according to the characters in the word. If we reach the end of the word and the last node is marked as "end of word", the word exists. If we can't find a path for all characters or the end node is not marked "end of word", the word doesn't exist.

📌 3. Prefix Search

Similar to search, but we stop at the node representing the end of the prefix. All words under that node have the given prefix.


                  #include 
                  #include 
                  #include 
              
                  using namespace std;
              
                  struct TrieNode {
                      TrieNode* children[26]; // Assuming lowercase English alphabets
                      bool isEndOfWord;
              
                      TrieNode() {
                          for (int i = 0; i < 26; i++) {
                              children[i] = nullptr;
                          }
                          isEndOfWord = false;
                      }
                  };
              
                  void insert(TrieNode* root, string word) {
                      TrieNode* curr = root;
                      for (char c : word) {
                          int index = c - 'a';
                          if (curr->children[index] == nullptr) {
                              curr->children[index] = new TrieNode();
                          }
                          curr = curr->children[index];
                      }
                      curr->isEndOfWord = true;
                  }
              
                  bool search(TrieNode* root, string word) {
                      TrieNode* curr = root;
                      for (char c : word) {
                          int index = c - 'a';
                          if (curr->children[index] == nullptr) {
                              return false;
                          }
                          curr = curr->children[index];
                      }
                      return curr->isEndOfWord;
                  }
              
                  bool startsWith(TrieNode* root, string prefix) {
                    TrieNode* curr = root;
                    for (char c : prefix) {
                        int index = c - 'a';
                        if (curr->children[index] == nullptr) {
                            return false;
                        }
                        curr = curr->children[index];
                    }
                    return true; // Prefix found (doesn't have to be a complete word)
                  }
              
                  int main() {
                      TrieNode* root = new TrieNode();
              
                      insert(root, "cat");
                      insert(root, "car");
                      insert(root, "dog");
                      insert(root, "dot");
                      insert(root, "cab");
              
                      cout << "Searching for 'cat': " << search(root, "cat") << endl;    // Output: 1 (true)
                      cout << "Searching for 'carpet': " << search(root, "carpet") << endl; // Output: 0 (false)
                      cout << "Starts with 'ca': " << startsWith(root, "ca") << endl; // Output: 1 (true)
              
                      return 0;
                  }

⏳ Time Complexity Analysis

Insertion and search operations in a Trie have a time complexity of O(m), where m is the length of the word.

🌍 Real-World Applications of Tries

⌨️ Autocompletion in search engines and IDEs.
✔️ Spell checkers.
🌐 IP routing.
🗂️ Storing dictionaries.