Understanding Prefix Trees

A prefix tree, commonly known as a Trie, is a specialized tree structure designed for efficient string storage and retrieval. Each node in a Trie represents a character, and the path from the root to a node represents a prefix. This structure excels in applications like autocomplete systems and spell checkers.

Initial Implementation Challenges

When first approaching this problem, one might consider a naive approach using a simple list to store strings. While functional, this method lacks efficiency:

class BasicTrie:
    def __init__(self):
        self.word_list = []

    def add_word(self, word: str) -> None:
        self.word_list.append(word)

    def contains(self, word: str) -> bool:
        return word in self.word_list

    def has_prefix(self, prefix: str) -> bool:
        for stored_word in self.word_list:
            if stored_word.startswith(prefix):
                return True
        return False

Efficient Trie Implementation

The optimal solution uses a node-based structure where each node contains an array of child references and a completion flag:

• Children array of size 26 (for lowercase English letters)
• Boolean flag marking the end of a complete word

Node Structure

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

Core Operations

Word Insertion

Traverse the Trie character by character, creating nodes as needed:

def insert_word(self, word: str) -> None:
    current = self.root
    for character in word:
        index = ord(character) - 97
        if current.next[index] is None:
            current.next[index] = TrieNode()
        current = current.next[index]
    current.word_complete = True

Prefix Search

Navigate through the structure following the prefix path:

def find_prefix(self, prefix: str):
    current = self.root
    for character in prefix:
        index = ord(character) - 97
        if current.next[index] is None:
            return None
        current = current.next[index]
    return current

Complete Word Search

Verify both prefix existence and completion flag:

def word_exists(self, word: str) -> bool:
    final_node = self.find_prefix(word)
    return final_node is not None and final_node.word_complete

Prefix Verification

def prefix_exists(self, prefix: str) -> bool:
    return self.find_prefix(prefix) is not None

Complete Implementation

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word: str) -> None:
        current = self.root
        for char in word:
            idx = ord(char) - 97
            if current.next[idx] is None:
                current.next[idx] = TrieNode()
            current = current.next[idx]
        current.word_complete = True
    
    def search(self, word: str) -> bool:
        result = self._traverse(word)
        return result is not None and result.word_complete
    
    def startsWith(self, prefix: str) -> bool:
        return self._traverse(prefix) is not None
    
    def _traverse(self, sequence: str):
        current = self.root
        for char in sequence:
            idx = ord(char) - 97
            if current.next[idx] is None:
                return None
            current = current.next[idx]
        return current

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

This implementation provides O(m) time complexity for all operations, where m is the length of the input string, making it significantly more efficient than the naive approach for large datasets.