Course contentsShow
← Computer Science
Lesson 620 of 2,87215. Tries and Specialized TreesFree lesson

Trie Node Structure and Components

Defining the structure of a trie node with character links and end-of-word markers for string representation.

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:

  1. Character Links (Children): An array or map that points to child nodes, one for each possible next character
  2. 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 isEndOfWord flag

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.