# LeetCode 208: Implement Trie Prefix Tree — Step-by-Step Visual Trace

**Medium** — Trie | Tree | Design | String

## The Problem

Implement a Trie (prefix tree) data structure that supports inserting words, searching for complete words, and checking if any words start with a given prefix.

## Approach

Use a tree structure where each node contains a dictionary of children nodes (one for each possible character) and a boolean flag to mark word endings. Traverse the tree character by character for all operations, creating new nodes during insertion as needed.

**Time:** O(m) where m is the length of the word/prefix for all operations · **Space:** O(ALPHABET_SIZE * N * M) where N is the number of words and M is the average length

## Code

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

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

    def insert(self, word: str) -> None:
        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: str) -> bool:
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end

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

# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)
```

## Watch It Run

> **[Open interactive visualization](https://tracelit.dev/app?trace=0208_implement-trie-prefix-tree)**

> **Try it yourself:** Open [TraceLit](https://tracelit.dev/app?trace=0208_implement-trie-prefix-tree) and step through every line.

---

*Built with [TraceLit](https://tracelit.dev) — the visual algorithm tracer for LeetCode practice.*