Problem Description

This problem asks you to implement a Trie (also known as a prefix tree), which is a tree-like data structure designed for efficient storage and retrieval of strings.

You need to create a Trie class with the following operations:

1. Trie(): Constructor that initializes an empty trie.

2. insert(word): Takes a string word and adds it to the trie. After insertion, the word should be stored in the trie structure.

3. search(word): Takes a string word and checks if the exact word exists in the trie. Returns true if the word was previously inserted, false otherwise.

4. startsWith(prefix): Takes a string prefix and checks if any word in the trie starts with this prefix. Returns true if at least one previously inserted word begins with the given prefix, false otherwise.

The key distinction between search and startsWith is that search looks for complete words that were inserted, while startsWith only checks if the given string is a prefix of any inserted word.

For example:

• After inserting "apple", search("apple") returns true
• search("app") returns false (since "app" was never inserted as a complete word)
• startsWith("app") returns true (since "app" is a prefix of "apple")

The implementation uses a tree structure where each node can have up to 26 children (one for each lowercase letter a-z), and each node has a boolean flag is_end to mark whether it represents the end of a complete word.

Intuition

Think about how we naturally organize words with common prefixes - like in a dictionary where "cat", "cats", and "category" are grouped together because they share the prefix "cat". This natural grouping suggests a tree structure where common prefixes share the same path from the root.

The key insight is that we can represent each character as a branch in our tree. Starting from the root, we follow a path down the tree for each character in a word. For example, inserting "cat" would create a path: root → c → a → t.

Since we're dealing with lowercase English letters only, each node needs at most 26 children (one for each letter a-z). We can use an array of size 26 where children[0] represents 'a', children[1] represents 'b', and so on. This gives us O(1) access to any child node by calculating the index as ord(character) - ord('a').

The challenge is distinguishing between a complete word and just a prefix. For instance, if we insert both "cat" and "category", the path for "cat" is contained within the path for "category". We need a way to mark that "cat" is a complete word, not just a prefix. This is where the is_end flag comes in - we set it to True at the node representing the last character of each inserted word.

For searching, we traverse the tree following the characters of the target word. If we can follow the complete path and the final node has is_end = True, we've found the word. For prefix checking, we only need to verify that we can follow the path for all characters in the prefix - we don't care about the is_end flag.

This approach naturally handles the shared prefix problem efficiently. Instead of storing "cat", "cats", and "category" as three separate strings (which would duplicate the "cat" prefix three times), we store the shared prefix once and branch out only where the words differ.

Solution Approach

The implementation uses a tree structure where each node contains an array of 26 child pointers and a boolean flag to mark word endings.

Node Structure: Each Trie node has:

• self.children: An array of size 26, initialized with None values. Each index corresponds to a letter ('a' at index 0, 'b' at index 1, etc.)
• self.is_end: A boolean flag set to False initially, marking whether this node represents the end of a complete word

Insert Operation:

def insert(self, word: str) -> None:
    node = self
    for c in word:
        idx = ord(c) - ord('a')
        if node.children[idx] is None:
            node.children[idx] = Trie()
        node = node.children[idx]
    node.is_end = True

Starting from the root, we traverse character by character:

1. Calculate the index for each character using ord(c) - ord('a') (converts 'a' to 0, 'b' to 1, etc.)
2. If no child exists at that index, create a new Trie node
3. Move to the child node and continue with the next character
4. After processing all characters, mark the final node with is_end = True

Helper Method - Search Prefix:

def _search_prefix(self, prefix: str):
    node = self
    for c in prefix:
        idx = ord(c) - ord('a')
        if node.children[idx] is None:
            return None
        node = node.children[idx]
    return node

This helper method traverses the trie following the path of the given prefix:

1. For each character, calculate its index and check if a child exists
2. If any character doesn't have a corresponding child, return None (prefix doesn't exist)
3. If all characters are found, return the final node reached

Search Operation:

def search(self, word: str) -> bool:
    node = self._search_prefix(word)
    return node is not None and node.is_end

To search for a complete word:

1. Use _search_prefix to find the node representing the last character
2. Return True only if the node exists AND is_end is True (confirming it's a complete word, not just a prefix)

StartsWith Operation:

def startsWith(self, prefix: str) -> bool:
    node = self._search_prefix(prefix)
    return node is not None

To check if any word starts with the given prefix:

1. Use _search_prefix to traverse the prefix path
2. Return True if we can successfully traverse all characters (node is not None)
3. We don't check is_end because we only care that the prefix exists, not whether it's a complete word

This implementation achieves O(m) time complexity for all operations where m is the length of the word/prefix, and uses O(ALPHABET_SIZE × N × m) space in the worst case, where N is the number of words inserted.

Example Walkthrough

Let's walk through a concrete example to understand how the Trie works:

Example Operations:

1. Insert "cat"
2. Insert "car"
3. Search "cat" → returns True
4. Search "ca" → returns False
5. StartsWith "ca" → returns True

Step-by-step visualization:

Initial State: Empty trie with just a root node

root (is_end=False)
  children: [None] * 26

Step 1: Insert "cat"

• Process 'c': idx = 2, create child at index 2
• Process 'a': idx = 0, create child at index 0
• Process 't': idx = 19, create child at index 19
• Mark the 't' node with is_end = True

root → [c] → [a] → [t] (is_end=True)

Step 2: Insert "car"

• Process 'c': idx = 2, child exists, move to it
• Process 'a': idx = 0, child exists, move to it (shared prefix!)
• Process 'r': idx = 17, create child at index 17
• Mark the 'r' node with is_end = True

        root
         |
        [c]
         |
        [a]
        / \
      [t] [r]
   (end)  (end)

Step 3: Search "cat"

• Call _search_prefix("cat"):
  • 'c': children[2] exists, move to it
  • 'a': children[0] exists, move to it
  • 't': children[19] exists, move to it
  • Returns the 't' node
• Check: node exists AND node.is_end = True
• Result: True ✓

Step 4: Search "ca"

• Call _search_prefix("ca"):
  • 'c': children[2] exists, move to it
  • 'a': children[0] exists, move to it
  • Returns the 'a' node
• Check: node exists BUT node.is_end = False
• Result: False ✗ (it's only a prefix, not a complete word)

Step 5: StartsWith "ca"

• Call _search_prefix("ca"):
  • 'c': children[2] exists, move to it
  • 'a': children[0] exists, move to it
  • Returns the 'a' node (not None)
• Check: node is not None
• Result: True ✓ (prefix exists in the trie)

Key Observations:

• "cat" and "car" share the prefix "ca", so they share the same path for those characters
• The is_end flag distinguishes complete words from prefixes
• Each character lookup is O(1) using array indexing
• The trie efficiently reuses common prefixes, saving space

Solution Implementation

Time and Space Complexity

Time Complexity

Insert Operation: O(m) where m is the length of the word being inserted.

• We traverse through each character of the word exactly once
• For each character, we perform constant time operations: calculating the index (ord(c) - ord('a')), checking if a child exists, creating a new node if needed, and moving to the next node
• Setting is_end = True at the end is O(1)

Search Operation: O(m) where m is the length of the word being searched.

• Calls _search_prefix which takes O(m) time
• Additionally checks the is_end flag which is O(1)
• Overall complexity remains O(m)

StartsWith Operation: O(p) where p is the length of the prefix.

• Directly calls _search_prefix which traverses through each character of the prefix
• Each character lookup is O(1) in the children array

_search_prefix Helper: O(p) where p is the length of the prefix.

• Iterates through each character in the prefix
• For each character, performs constant time array access and index calculation

Space Complexity

Per Node Space: Each Trie node contains:

• An array of 26 pointers (for lowercase English letters a-z): O(26) = O(1)
• A boolean flag is_end: O(1)

Overall Space Complexity: O(n × 26) = O(n) where n is the total number of nodes in the Trie.

• In the worst case, if we insert k words with average length m and no common prefixes, we would have k × m nodes
• In the best case with maximum prefix sharing, we could have as few as m nodes (all words share the same path)
• The space complexity is proportional to the total number of unique prefixes across all inserted words

Space per Operation:

• Insert: O(m) in worst case when creating m new nodes for a word of length m
• Search and StartsWith: O(1) additional space (only using variables for traversal)

Common Pitfalls

1. Confusing Node Creation Logic

A frequent mistake is creating unnecessary Trie nodes or incorrectly checking for existing nodes during insertion.

Incorrect Implementation:

def insert(self, word: str) -> None:
    node = self
    for c in word:
        idx = ord(c) - ord('a')
        node.children[idx] = Trie()  # Always creates new node, overwriting existing ones!
        node = node.children[idx]
    node.is_end = True

Why it's wrong: This overwrites existing nodes, destroying previously inserted words that share prefixes.

Correct Approach:

def insert(self, word: str) -> None:
    node = self
    for c in word:
        idx = ord(c) - ord('a')
        if node.children[idx] is None:  # Only create if doesn't exist
            node.children[idx] = Trie()
        node = node.children[idx]
    node.is_end = True

2. Forgetting the is_end Flag in Search

Many implementations forget to check if a node marks the end of a word, causing incorrect search results.

Incorrect Implementation:

def search(self, word: str) -> bool:
    node = self._search_prefix(word)
    return node is not None  # Missing is_end check!

Why it's wrong: This would return True for "app" even if only "apple" was inserted, since "app" exists as a prefix.

Correct Approach:

def search(self, word: str) -> bool:
    node = self._search_prefix(word)
    return node is not None and node.is_end  # Must check both conditions

3. Character Index Calculation Errors

Incorrect index calculation can lead to array out-of-bounds errors or wrong character mappings.

Common Mistakes:

# Wrong: Using character directly as index
idx = ord(c)  # Could be 97-122, exceeding array bounds!

# Wrong: Subtracting wrong base
idx = ord(c) - ord('A')  # Wrong for lowercase letters

# Wrong: Not handling the case properly
idx = c - 'a'  # Python doesn't support direct char arithmetic

Correct Approach:

idx = ord(c) - ord('a')  # Converts 'a'->0, 'b'->1, ..., 'z'->25

4. Memory Inefficiency with Full Node Initialization

Creating all 26 children immediately for every node wastes memory.

Inefficient:

def __init__(self):
    self.children = [Trie() for _ in range(26)]  # Creates 26 nodes immediately!
    self.is_end = False

Efficient:

def __init__(self):
    self.children = [None] * 26  # Only creates array, nodes created on demand
    self.is_end = False

5. Not Handling Edge Cases

Failing to consider empty strings or special cases.

Potential Issues:

• Inserting empty string ""
• Searching for empty string
• Inserting the same word multiple times

Robust Solution:

def insert(self, word: str) -> None:
    if not word:  # Handle empty string
        self.is_end = True  # Mark root as end if needed
        return
  
    node = self
    for c in word:
        idx = ord(c) - ord('a')
        if node.children[idx] is None:
            node.children[idx] = Trie()
        node = node.children[idx]
    node.is_end = True

6. Incorrect Variable Naming Leading to Confusion

Using inconsistent naming between is_end and is_end_of_word can cause attribute errors.

Error-Prone:

# In __init__:
self.is_end_of_word = False

# But in insert:
node.is_end = True  # AttributeError!

Solution: Use consistent naming throughout the implementation.