Trie Implementation and Operations

Problem Statement

Implement the Trie class:

• Trie(): Initializes the trie object.
• void insert (String word): Inserts the string word into the trie.
• boolean search (String word): Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
• boolean startsWith (String prefix): Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Approach

1️⃣ To insert a Node in The Trie:

• Begin at the root node.
• For each character in the word:
  • Check if the current node has a child node for the character.
  • If the child node doesn't exist, create a new node and link it to the current node.
  • Move to the child node that corresponds to the character.
• After inserting all characters, mark the end of the word by setting the end flag of the last node to true.

2️⃣ To Search for a word in Trie:

• Begin at the root node.
• For each character in the word:
  • Verify if the current node has a child node for the character.
  • If not, the word is not present in the Trie.
  • Move to the child node corresponding to the character.
• After processing all characters, check if the end flag of the last node is set to true. If it is, the word is found; if not, the word is not in the Trie.

3️⃣ Check if Trie contains Prefix:

• Begin at the root node.
• For each character in the prefix:
  • Check if the current node has a child node for the character.
  • If it doesn't, there is no word with the given prefix.
  • Move to the child node that corresponds to the character.
• If all characters of the prefix are found, return true to indicate that there are words with the given prefix.

Code in C++:

class TrieNode {
public:
    TrieNode* children[26]; // Array to store pointers to child nodes (assuming only lowercase English letters)
    bool isEndOfWord;       // Indicates whether this node represents the end of a word

    // Constructor: Initialize children to nullptr and isEndOfWord to false
    TrieNode() {
        isEndOfWord = false;
        for (int i = 0; i < 26; i++) {
            children[i] = nullptr;
        }
    }
};

class Trie {
private:
    TrieNode* root; // Root node of the trie

public:
    // Constructor: Initialize the trie with a root node
    Trie() {
        root = new TrieNode();
    }

    // Function to insert a word into the trie
    void insert(string word) {
        TrieNode* node = root; // Start from the root
        for (char ch : word) { // Iterate through each character in the word
            int index = ch - 'a'; // Calculate index in children array (0 for 'a', 1 for 'b', etc.)
            if (node->children[index] == nullptr) { // If no node exists for the current character
                node->children[index] = new TrieNode(); // Create a new node
            }
            node = node->children[index]; // Move to the child node
        }
        node->isEndOfWord = true; // Mark the last node as the end of a word
    }

    // Function to search for a word in the trie
    bool search(string word) {
        TrieNode* node = root; // Start from the root
        for (char ch : word) { // Iterate through each character in the word
            int index = ch - 'a'; // Calculate index in children array
            if (node->children[index] == nullptr) { // If the path for the current character doesn't exist
                return false; // The word is not in the trie
            }
            node = node->children[index]; // Move to the child node
        }
        return node->isEndOfWord; // Return true if the word ends at the current node
    }

    // Function to check if any word starts with the given prefix
    bool startsWith(string prefix) {
        TrieNode* node = root; // Start from the root
        for (char ch : prefix) { // Iterate through each character in the prefix
            int index = ch - 'a'; // Calculate index in children array
            if (node->children[index] == nullptr) { // If the path for the current character doesn't exist
                return false; // No word with the given prefix
            }
            node = node->children[index]; // Move to the child node
        }
        return true; // Return true if the prefix exists in the trie
    }
};

Complexity Analysis:

• Time Complexity:
  • Insertion: O(N), where N is the length of the word being inserted. This is because we need to go through each letter of the word to either find its corresponding node or create a new node as needed.
  • Search: O(N), where N is the length of the word being searched for. During a Trie search, we traverse each letter of the word starting from the root, checking if the current node has a child node at the position of the next letter. This continues until we either reach the end of the word or find a missing letter node.
  • Prefix Search: O(N), where N is the length of the prefix being searched for. Just like in word search, we go through each letter of the prefix to find its corresponding node.
• Space Complexity: O(N) where N is the total number of characters across all unique words inserted into the Trie. For each character in a word, a new node might need to be created, resulting in space usage that is proportional to the total number of characters.