Implement Trie (Prefix Tree) — Step-by-Step Visualization

Algorithm Pattern

Prefix Tree (Trie) Node Design

Key Idea

A Trie is a tree where each node represents a single character of a string. The root node is usually empty. Each node has: 1. A dictionary or array of children (mapping character to the next TrieNode). 2. A boolean flag `isEndOfWord` to indicate if a complete word ends at this node. This allows for prefix searches and word lookups in $O(L)$ time, where $L$ is the length of the string.

Step-by-Step Approach

1. Define `TrieNode` with `children = {}` and `isEndOfWord = False`.
2. Insert(word): Start at root, for each char, create a child if it doesn't exist. Mark last node `isEndOfWord = True`.
3. Search(word): Start at root, for each char, follow child. If node missing, return `False`. Else return `node.isEndOfWord`.
4. StartsWith(prefix): Same as search, but return `True` as long as you can follow the path to the end of the prefix.

Common Gotchas

• The 'startsWith' check only requires the nodes to exist, while 'search' requires the final node to have the end-of-word flag set.