Trie Insertion: Adding Words
What you'll learn: How to implement the insertion operation that adds a string to a trie by creating nodes character by character along the path.
The Core Idea
Inserting a word into a trie means walking down from the root, following (or creating) edges labeled with each character of the word in sequence. Think of it like carving a path through a forest—if the trail already exists, you walk it; if not, you blaze a new section.
Starting at the root, you examine the first character. If a child node with that character already exists, move to it. If not, create a new child node for that character. Repeat this process for each subsequent character. When you've processed all characters, mark the final node as the end of a valid word (often using a boolean flag like isEndOfWord).
Step-by-Step Process
- Start at root: Begin with the root node (which typically represents an empty string)
- For each character in the word:
- Check if a child node exists for that character
- If yes, follow that link
- If no, create a new child node and link it
- Mark completion: Set the
isEndOfWordflag totrueat the final node
Example
Inserting "cat" then "car":
- Insert "cat": root → (create 'c') → (create 'a') → (create 't', mark end)
- Insert "car": root → (existing 'c') → (existing 'a') → (create 'r', mark end)
Notice how "ca" is shared between both words—this is the power of tries!
Time and Space
The insertion takes O(m) time where m is the length of the word (one operation per character). Space complexity is also O(m) for a completely new word, though shared prefixes reuse existing nodes.
Key Takeaway:
Trie insertion builds words character-by-character, creating new nodes only when necessary and marking the final node to signal a complete word.