Trie Node Structure

A trie node typically contains:

class TrieNode:
    children: map from char to TrieNode
    isEndOfWord: boolean

For lowercase English letters, you can use an array of 26 instead of a map:

class TrieNode:
    children: array of 26 TrieNodes (initially null)
    isEndOfWord: boolean

The isEndOfWord flag marks whether a complete word ends at this node.

Without it, you couldn't distinguish between "car" and "card" if both are in the trie. The path c→a→r exists for both.

Space complexity: $O(\text{ALPHABET\_SIZE} \cdot L \cdot N)$ where $N$ is number of words and $L$ is average length. In practice, prefix sharing means most words share nodes, so actual space is much smaller. Time: $O(L)$. Space: $O(L)$.