Trie Node Structure and Components
You'll learn: How to structure a trie node to efficiently store character links and track complete words.
The Core Structure
A trie node is simpler than you might expect. Each node needs just two essential components:
- Character Links (Children): An array or map that points to child nodes, one for each possible next character
- End-of-Word Marker: A boolean flag indicating whether a complete word ends at this node
Think of a trie node like a signpost at a crossroads. The signpost has multiple arrows (links) pointing to different paths (characters), and a special marker that says "a valid destination is HERE" (end-of-word flag).
Why This Design?
Unlike binary tree nodes that store actual values, trie nodes store relationships. The character isn't stored in the node itself—it's represented by the link from the parent. For example, if the root has a link at index 'a', following that link represents moving through the character 'a'.
The end-of-word marker is crucial. Without it, you couldn't distinguish between a stored word like "car" and just a prefix of "cart". When you reach the node after 'r' in "car", the marker tells you: "Yes, 'car' is a complete word in this trie."
Typical Structure
For English lowercase letters, you might have:
- An array of 26 child pointers (one per letter)
- A boolean
isEndOfWordflag
For more general use (any character), you'd use a hash map instead of a fixed array, trading some space efficiency for flexibility.
Key Takeaway: A trie node contains an array/map of links to children (representing possible next characters) and a boolean flag marking whether a valid word ends at that node.