> ## 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)

> Trie data structure for efficient string operations and prefix matching.

# 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

| Operation            | Time Complexity |
| -------------------- | --------------- |
| Insert               | O(m)            |
| Search               | O(m)            |
| Starts With (prefix) | O(m)            |
| Delete               | O(m)            |

Where **m** = length of the word/prefix.

## Implementation Skeleton

```python theme={null}
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)