Skip to main content

Documentation Index

Fetch the complete documentation index at: https://swe.aboneda.com/llms.txt

Use this file to discover all available pages before exploring further.

​
Trie (Prefix Tree)

A tree-like data structure used for efficient retrieval of keys in a dataset of strings.

​
Structure

  • Each node represents a single character
  • The root is empty; paths from root to marked nodes form stored words
  • Each node has up to 26 children (for lowercase English letters)
  • A boolean flag marks the end of a word

​
Core Operations

OperationTime Complexity
InsertO(m)
SearchO(m)
Starts With (prefix)O(m)
DeleteO(m)
Where m = length of the word/prefix.

​
Implementation Skeleton

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 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):
        node = self._find(word)
        return node is not None and node.is_end

    def starts_with(self, prefix):
        return self._find(prefix) is not None

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

​
Classic Problems

  • Implement Trie
  • Word Search II (backtracking + trie)
  • Design Add and Search Words
  • Replace Words
  • Longest Word in Dictionary
  • Auto-complete systems

​
When to Use

  • Prefix matching and auto-complete
  • Spell checkers and dictionary lookups
  • IP routing (longest prefix match)
  • Word games (Boggle, Scrabble solvers)