Trie

A Trie (prefix tree) is a tree specialized for storing strings. Each node represents a single character. The path from the root to a node forms a string or a prefix.

Trie Structure

        root
       / | \
      a   b   c
     /   / \   \
    p   a   e   a
   /   /     \   \
  p   d       t   r
 /   / \           \
l   d   d           t

Stores: "app", "add", "bad", "bat", "car", "cat"

Implementation

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

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

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

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

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

Usage

trie = Trie()
trie.insert("apple")
trie.insert("app")
trie.insert("banana")

print(trie.search("apple"))      # True
print(trie.search("app"))        # True
print(trie.search("ap"))         # False (prefix only, not a word)
print(trie.startsWith("ban"))    # True
print(trie.startsWith("bat"))    # False

Time Complexity

m = word length. Unaffected by the number of words in the trie.

Autocomplete

    def autocomplete(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return []
            node = node.children[char]

        results = []
        self._collect(node, prefix, results)
        return results

    def _collect(self, node, prefix, results):
        if node.is_end:
            results.append(prefix)
        for char, child in node.children.items():
            self._collect(child, prefix + char, results)

trie = Trie()
trie.insert("cat")
trie.insert("car")
trie.insert("card")
trie.insert("care")
trie.insert("dog")

print(trie.autocomplete("car"))  # ['car', 'card', 'care']

Trie vs Hash Table

Applications

• Autocomplete and spell checkers
• IP routing (longest prefix match)
• Word games (Scrabble, Boggle)
• Dictionary implementation

Tries are efficient for string search. Now let's study Graphs for data with complex relationships.