Implement Trie (Prefix Tree) | Leetcode 208 | Efficient String Data Structure

The Implement Trie (Prefix Tree) problem asks us to design a Trie data structure that supports the following operations:

1. Insert(word): Insert a word into the Trie.
2. Search(word): Return True if the word is in the Trie, False otherwise.
3. startsWith(prefix): Return True if there is any word in the Trie that starts with the given prefix.

A Trie (Prefix Tree) is a tree-like data structure that efficiently stores and retrieves strings, especially useful for prefix-based searches.

Here’s the [Problem Link] to begin with.

Examples

Example 1

Input:
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // returns True
trie.search("app");     // returns False
trie.startsWith("app"); // returns True
trie.insert("app");
trie.search("app");     // returns True

Intuition and Approach

The Trie is built using nodes where:

• Each node represents a character.
• Each node can have multiple children (for each possible next character).
• A special flag is_end_of_word marks whether a complete word ends at that node.

Steps:

1. Insert(word):
   • Start from the root.
   • For each character in the word:
     • If the character does not exist in the current node’s children, create a new node.
     • Move to that child node.
   • After processing all characters, mark the last node as is_end_of_word = True.
2. Search(word):
   • Start from the root.
   • Traverse character by character.
   • If at any point the character doesn’t exist, return False.
   • At the end, return True only if the final node is marked as end of a word.
3. startsWith(prefix):
   • Similar to search, but we do not check the is_end_of_word flag.
   • If all characters in the prefix exist, return True.

Code Implementation

class TrieNode:
    def __init__(self):
        # Each node holds up to 26 children (a–z), using a dict for flexibility
        self.children = {}
        # Flag to mark the end of a complete word
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        # Root node doesn't contain any character itself
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            # Create a new node if this character path doesn't exist
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        # Mark the final node as the end of a word
        node.is_end_of_word = True

    def search(self, word: str) -> bool:
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        # Return True only if the complete word exists (i.e., is marked as ended here)
        return node.is_end_of_word

    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        # If traversal succeeds, the prefix exists
        return True

Code Explanation

• TrieNode class:
  • Stores children in a dictionary.
  • Uses is_end_of_word to mark if a word ends at this node.
• Insert method:
  • Builds the path of characters.
  • Creates new nodes when required.
• Search method:
  • Traverses character by character.
  • Ensures the word ends at a valid terminal node.
• startsWith method:
  • Traverses only the prefix.
  • Does not require the end node to be marked.

Dry Run

Insert "apple" into the Trie:

• Root → 'a' → 'p' → 'p' → 'l' → 'e'
• Mark node 'e' as end of word.

Now:

• search("apple") → True
• search("app") → False (prefix exists but not marked as word)
• startsWith("app") → True

Time and Space Complexity

• Insert: O(L) where L = length of word.
• Search: O(L) where L = length of word.
• startsWith: O(P) where P = length of prefix.
• Space Complexity:
  • Each inserted character may create a new node.
  • Worst case = O(N * L) where N = number of words, L = average word length.

Conclusion

The Implement Trie (Prefix Tree) problem demonstrates how to build and use a Trie for efficient prefix-based searching.

• Supports insert, search, and startsWith operations.
• Each operation runs in linear time relative to the length of the input word/prefix.
• Widely used in applications like autocomplete, spell checking, and dictionary lookups.

This solution is both optimal and scalable, making it a must-know data structure for coding interviews.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.