deepSWE.io

Implement Trie (Prefix Tree)

Dynamic ProgrammingData Structures

Problem Statement

A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class with the following methods:

Trie() - Initializes the trie object
insert(word) - Inserts the string word into the trie
search(word) - Returns true if the string word is in the trie
startsWith(prefix) - Returns true if there is a previously inserted string that has the prefix

Example Trie Structure

Words inserted: apple, app, apricot, banana, band, bandana

Example queries:

search("app") → true
search("apple") → true
search("appl") → false
startsWith("app") → true
startsWith("ban") → true
startsWith("xyz") → false

Key Characteristics

• Each node represents a single character
• Root node is empty
• Path from root to any node forms a prefix
• End-of-word nodes are marked to distinguish complete words
• Time complexity: O(m) for insert, search, and startsWith operations
• Space complexity: O(ALPHABET_SIZE * N * M) where N is number of words and M is average length

Algorithm Explanation

A Trie (prefix tree) is a tree data structure that stores strings efficiently by sharing common prefixes. Each node represents a character, and paths from root to nodes form prefixes.

Key Operations

Insert: Add a word by traversing/creating nodes for each character. Mark the final node as end-of-word.
Search: Traverse the trie following the word's characters. Return true if we reach a node marked as end-of-word.
StartsWith: Similar to search, but return true if we can traverse all prefix characters, regardless of end-of-word status.

Dynamic Programming Aspects

Memoization: Each node stores the result of "does this prefix exist" to avoid recomputation.
Optimal Substructure: Finding a word depends on finding its prefixes.
Overlapping Subproblems: Multiple words share common prefixes, avoiding redundant storage.

Trie Insertion Demonstration

Inserting "cap" into a trie that already contains "cat" and "car"

Start: Initialize trie insertion

Starting insertion of "cap". Begin at root node.

Inserting word: "cap"

CAP

Step 1 of 5

Current Node

End of Word

Regular Node

Implement Trie (Prefix Tree) Solution


class TrieNode:
    def __init__(self):
        """
        Initialize a TrieNode with children dictionary and end of word flag.
        Each node can have up to 26 children (for lowercase letters).
        """
        self.children = {}  # Dictionary to store child nodes
        self.is_end_of_word = False  # Flag to mark end of a word

class Trie:
    def __init__(self):
        """
        Initialize the Trie data structure.
        The root node represents an empty character.
        """
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        """
        Insert a word into the trie.
        
        Time Complexity: O(m) where m is the length of the word
        Space Complexity: O(m) in worst case when all characters are new
        
        Args:
            word: The word to insert into the trie
        """
        current = self.root
        
        # Traverse each character in the word
        for char in word:
            # If character doesn't exist, create new node
            if char not in current.children:
                current.children[char] = TrieNode()
            
            # Move to the child node
            current = current.children[char]
        
        # Mark the end of the word
        current.is_end_of_word = True

    def search(self, word: str) -> bool:
        """
        Search for a complete word in the trie.
        
        Time Complexity: O(m) where m is the length of the word
        Space Complexity: O(1)
        
        Args:
            word: The word to search for
            
        Returns:
            True if the word exists as a complete word, False otherwise
        """
        current = self.root
        
        # Traverse each character in the word
        for char in word:
            # If character doesn't exist, word is not in trie
            if char not in current.children:
                return False
            
            # Move to the child node
            current = current.children[char]
        
        # Return True only if we've reached end of a complete word
        return current.is_end_of_word

    def startsWith(self, prefix: str) -> bool:
        """
        Check if any word in the trie starts with the given prefix.
        
        Time Complexity: O(p) where p is the length of the prefix
        Space Complexity: O(1)
        
        Args:
            prefix: The prefix to search for
            
        Returns:
            True if any word starts with the prefix, False otherwise
        """
        current = self.root
        
        # Traverse each character in the prefix
        for char in prefix:
            # If character doesn't exist, no words with this prefix
            if char not in current.children:
                return False
            
            # Move to the child node
            current = current.children[char]
        
        # If we can traverse all prefix characters, prefix exists
        return True

# Example usage and testing
if __name__ == "__main__":
    # Create a new Trie instance
    trie = Trie()
    
    # Insert some words
    trie.insert("apple")
    trie.insert("app")
    trie.insert("application")
    
    # Test search functionality
    print(trie.search("app"))         # True
    print(trie.search("apple"))       # True
    print(trie.search("appl"))        # False
    
    # Test prefix functionality
    print(trie.startsWith("app"))     # True
    print(trie.startsWith("application")) # True
    print(trie.startsWith("xyz"))     # False