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

Trie Insertion: Adding Words

Implementing the insertion operation to add strings to a trie by creating nodes along the character path.

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

  1. Start at root: Begin with the root node (which typically represents an empty string)
  2. 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
  3. Mark completion: Set the isEndOfWord flag to true at 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.