Trie (Prefix Tree)

Overview

Tree-like structure for storing strings character by character. Optimised for prefix operations.

vs HashMap: HashMap gives O(1) exact match. Trie gives O(m) prefix matching — no hashmap equivalent.

Use for: autocomplete, spell-check, IP routing, word search on a grid.

---

Implementation (Class-based — interview standard)

class TrieNode:
    def __init__(self):
        self.children = {}   # char -> TrieNode
        self.is_end = False

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

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def search(self, word: str) -> bool:
        node = self.root
        for ch in word:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return node.is_end

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

---

Implementation (Dict-based — compact)

class Trie:
    def __init__(self):
        self.root = {}
        self.END = "*"

    def insert(self, word):
        curr = self.root
        for ch in word:
            if ch not in curr:
                curr[ch] = {}
            curr = curr[ch]
        curr[self.END] = True

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

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

---

Advanced Operations

# Get all words with a given prefix
def words_with_prefix(self, prefix):
    words = []
    curr = self.root
    for ch in prefix:
        if ch not in curr.children:
            return []
        curr = curr.children[ch]
    self._dfs(curr, prefix, words)
    return words

def _dfs(self, node, current, words):
    if node.is_end:
        words.append(current)
    for ch, child in node.children.items():
        self._dfs(child, current + ch, words)

# Find longest common prefix
def longest_common_prefix(self):
    curr = self.root
    prefix = ""
    while len(curr.children) == 1 and not curr.is_end:
        ch = next(iter(curr.children))
        prefix += ch
        curr = curr.children[ch]
    return prefix

# Find all matches in a document
def find_matches(self, document):
    matches = set()
    for i in range(len(document)):
        curr = self.root
        for j in range(i, len(document)):
            ch = document[j]
            if ch not in curr.children:
                break
            curr = curr.children[ch]
            if curr.is_end:
                matches.add(document[i:j+1])
    return matches

---

Interview Patterns → see [[Tries]]