# Trie (Prefix Tree)

## Problem Description

Implement a Trie (also called Prefix Tree) data structure for efficient string storage and retrieval, particularly useful for prefix-based operations.

## What is a Trie?

A trie is a tree-like data structure used to store strings where each node represents a character. Words with common prefixes share the same path from the root, making it efficient for prefix operations.

## Characteristics

- **Time Complexity**:
  - Insert: O(m) where m is the length of the word
  - Search: O(m)
  - StartsWith: O(m)
  - Delete: O(m)
- **Space Complexity**: O(ALPHABET_SIZE * N * M) where N is number of words and M is average length
- **Best for**: Prefix operations, autocomplete, spell checking

## Structure

Each TrieNode contains:
- Map of character to child TrieNode
- Boolean flag indicating end of word

```
Trie with "cat", "car", "dog":
       root
      /   \
     c     d
     |     |
     a     o
    / \    |
   t   r   g
   *   *   *
(* = end of word)
```

## Core Operations

1. **insert(word)**: Add a word to the trie
2. **search(word)**: Check if exact word exists
3. **startsWith(prefix)**: Check if any word starts with prefix
4. **delete(word)**: Remove a word from trie
5. **wordsWithPrefix(prefix)**: Get all words with given prefix

## Your Task

Implement the following methods in `Trie.java`:

1. `insert(String word)` - Insert a word
2. `search(String word)` - Search for exact match
3. `startsWith(String prefix)` - Check for prefix
4. `delete(String word)` - Delete a word
5. `wordsWithPrefix(String prefix)` - Find all words with prefix

## Test Cases to Consider

- Insert and search words
- Search for non-existent words
- Check prefixes
- Words that are prefixes of other words ("app" and "apple")
- Empty string
- Delete words
- Single character words
- Words with common prefixes

## Hints

- Use a HashMap<Character, TrieNode> for children
- Mark end of word with a boolean flag
- For search: traverse to end and check isEndOfWord
- For startsWith: just check if path exists
- For delete: use recursion and clean up nodes with no children

## Insert Algorithm

```
1. Start at root
2. For each character in word:
   - If child doesn't exist, create it
   - Move to child
3. Mark last node as end of word
```

## Search Algorithm

```
1. Start at root
2. For each character in word:
   - If child doesn't exist, return false
   - Move to child
3. Check if current node is marked as end of word
```

## Applications

- Autocomplete systems
- Spell checkers
- IP routing (longest prefix matching)
- T9 predictive text
- Solving word games (Boggle, Scrabble)
- Dictionary implementation
- Search engines

## Advantages over Hash Table

1. Can quickly find all words with given prefix
2. Alphabetical ordering of words
3. No hash collisions
4. Predictable lookup time

## Disadvantages

1. More memory intensive
2. Cache-unfriendly (pointer chasing)
3. More complex to implement

## Follow-up Questions

1. How would you implement word count (number of times a word is inserted)?
2. How would you find the longest word in the trie?
3. How would you implement a case-insensitive trie?
4. Can you optimize space by compressing common paths?

## Variations

1. **Radix Tree (Patricia Trie)**: Compressed trie
2. **Suffix Tree**: For substring operations
3. **Ternary Search Tree**: Space-efficient variant
4. **Compressed Trie**: Merge nodes with single child

## Common Pitfalls

- Not marking end of word correctly
- Forgetting to handle words that are prefixes of others
- Memory leaks in delete operation
- Not handling empty string
- Case sensitivity issues

## Delete Operation Considerations

When deleting:
1. Check if word exists
2. Remove end-of-word marker
3. Clean up nodes with no children (optional optimization)
4. Don't delete nodes that are part of other words

## Comparison with BST

| Operation | Trie | BST |
|-----------|------|-----|
| Search | O(m) | O(log n) |
| Insert | O(m) | O(log n) |
| Space | Higher | Lower |
| Use Case | Prefix ops | General |

m = word length, n = number of words

## Practice Problems

1. Implement autocomplete
2. Word search in 2D grid
3. Replace words (longest prefix)
4. Design search autocomplete system
5. Longest word in dictionary
6. Stream of characters

## Related Data Structures

- Hash Table
- Binary Search Tree
- Suffix Tree
- Radix Tree