# Trie — Data Structures & Algorithms

Source: https://www.geekswithgeeks.com/en/dsa/trie

> A prefix tree: one node per character, sharing common prefixes.

## Words as paths

Each word is a path from the root, one edge per character. `cat` and `car` share the `c-a` path then branch. Lookup, insert, and prefix checks are `O(L)` where `L` is the word length — independent of how many words are stored.

## Insert & search

A node is just a map of child characters plus an end-of-word flag.

```python
class Trie:
    def __init__(self):
        self.root = {}
    def insert(self, word):
        node = self.root
        for c in word:
            node = node.setdefault(c, {})
        node['$'] = True          # word ends here
    def search(self, word):
        node = self.root
        for c in word:
            if c not in node: return False
            node = node[c]
        return '$' in node
```

## Phone contacts

Type 'Jo' and the phone instantly narrows to John, Joanna, Joseph. It's walked two edges down a trie of names.

## Where it hides

Autocomplete, spell-check, IP routing tables, and word-search / prefix problems. Trade-off: heavy pointer overhead per character.