Node Structure

A trie node holds:

• Children pointers (one per possible next char)
• An "is end of word" flag

For ASCII a-z, you can use a 26-element array — faster than a hash map. For Unicode, a hash map is necessary.

Memory: each node with N children consumes ~N pointers. For a 26-letter array: 26 * 8 bytes = 208 bytes per node minimum. A trie with 100k English words can use ~10 MB — efficient for the prefix-search benefit.

For SUFFIX queries (find all words ending in ing), you'd build a separate trie of REVERSED strings.

Pruning empty branches reduces memory: a node with no children and not a word can be deleted. For huge tries, radix trees (path compression) reduce node count further.