Understanding Trie Data Structure

A Trie (pronounced 'try', from retrieval) is a tree-like data structure used to efficiently store and search a dynamic set of strings, especially useful for prefix-based operations like autocomplete.

Structure

Each node in a Trie represents a single character. A path from the root to a node represents a prefix, and a special marker (often a boolean flag) indicates whether that path represents a complete word.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

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

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_end_of_word = True

    def search(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return node.is_end_of_word

    def starts_with(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return True

Complexity

Applications

• Autocomplete and typeahead suggestions.
• Spell checkers.
• IP routing (longest prefix match).
• Dictionary implementations with fast prefix lookups.