Implement Trie (Prefix Tree)

How it works

A Prefix Tree (Trie) is a tree-like data structure designed for fast string operations.

Each node represents a character, and paths from the root represent words.

• Common prefixes are shared, which saves space.
• Each node has 26 children (for letters a-z), indexed directly using character positions.
• A boolean flag endOfWord tells us whether a complete word ends at that node.

Why Trie is useful:

• Searching words and prefixes is O(length of word), not dependent on how many words exist.
• Ideal for problems involving dictionary lookups, autocomplete, and prefix checks.

Steps

Data Structure

• Each node contains:
  • children[26]: array of child pointers (one for each letter)
  • endOfWord: marks completion of a word

---

Insert(word)

1. Start from the root.
2. For each character in the word:
   • Convert character to index (c - 'a')
   • If the child node doesn’t exist, create it.
   • Move to the child.
3. After processing all characters, mark endOfWord = true.

---

Search(word)

1. Start from the root.
2. For each character:
   • Move to the corresponding child.
   • If missing, return false.
3. After traversal:
   • Return true only if endOfWord is true.

---

StartsWith(prefix)

1. Start from the root.
2. Traverse characters of the prefix.
3. If all characters exist in sequence, return true.
4. No need to check endOfWord.

Complexity

• Time complexity: O(n) for each function call.
• Space complexity: O(t)

Where n is the length of the string and t is the total number of TrieNodes created in the Trie.

Things to watch for

Confusing search and startsWith

A frequent mistake is returning true in search() whenever the traversal completes successfully, without checking the endOfWord flag. The search() method must verify that the final node marks the end of a complete word, while startsWith() only checks if the prefix path exists. For example, if "apple" is inserted, search("app") should return false (no word ends there), but startsWith("app") should return true.

Incorrect Character Index Calculation

When using an array-based Trie with 26 children, the character must be converted to an index using c - 'a'. A common error is using the ASCII value directly without subtraction, which causes index out of bounds errors. Another mistake is assuming uppercase letters, which would require c - 'A' instead. Always ensure the input constraints match the indexing scheme.

Forgetting to Initialize Child Nodes

When traversing during insert(), forgetting to create a new TrieNode when the child does not exist leads to null pointer exceptions on subsequent character accesses. The check if cur.children[i] == None: cur.children[i] = TrieNode() must happen before moving to the next node. Similarly, in the hash map approach, forgetting to add the character key before accessing it causes key errors.

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

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

    def insert(self, word: str) -> None:
        cur = self.root
        for c in word:
            i = ord(c) - ord("a")
            if cur.children[i] == None:
                cur.children[i] = TrieNode()
            cur = cur.children[i]
        cur.endOfWord = True

    def search(self, word: str) -> bool:
        cur = self.root
        for c in word:
            i = ord(c) - ord("a")
            if cur.children[i] == None:
                return False
            cur = cur.children[i]
        return cur.endOfWord

    def startsWith(self, prefix: str) -> bool:
        cur = self.root
        for c in prefix:
            i = ord(c) - ord("a")
            if cur.children[i] == None:
                return False
            cur = cur.children[i]
        return True

class TrieNode {
public:
    TrieNode* children[26];
    bool endOfWord;

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

class PrefixTree {
    TrieNode* root;

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

    void insert(string word) {
        TrieNode* cur = root;
        for (char c : word) {
            int i = c - 'a';
            if (cur->children[i] == nullptr) {
                cur->children[i] = new TrieNode();
            }
            cur = cur->children[i];
        }
        cur->endOfWord = true;
    }

    bool search(string word) {
        TrieNode* cur = root;
        for (char c : word) {
            int i = c - 'a';
            if (cur->children[i] == nullptr) {
                return false;
            }
            cur = cur->children[i];
        }
        return cur->endOfWord;
    }

    bool startsWith(string prefix) {
        TrieNode* cur = root;
        for (char c : prefix) {
            int i = c - 'a';
            if (cur->children[i] == nullptr) {
                return false;
            }
            cur = cur->children[i];
        }
        return true;
    }
};