Introduction to Tries - Inserting Words

You're sitting in your Amazon interview when the interviewer pulls up a blank editor and says, "Let's talk about how search engines suggest words as you type." Before you can answer, they follow up: "Implement the insert method for a Trie." This is one of those problems that separates candidates who truly understand data structures from those who've only memorized solutions. The Trie, also known as a prefix tree on platforms like LeetCode and NeetCode, is a foundational building block behind autocomplete, spell checkers, and IP routing tables.

TL;DR

A Trie stores words character by character in a tree structure where shared prefixes share the same path. To insert a word, start at the root and walk down the tree one character at a time. If a child node for the current character doesn't exist, create it. After processing the last character, mark that node as a word boundary. This runs in O(k) time where k is the word length, with O(n * k) total space for n words.

Why This Problem Matters

The Trie is one of those data structures that doesn't come up in daily coding but appears repeatedly in interviews, especially at Amazon, Google, and Microsoft. Understanding how insertion works is the gateway to solving harder Trie problems like autocomplete, word search in grids, and longest common prefix. If you can build a Trie from scratch, you can tackle all of these confidently.

What is a Trie?

A Trie (pronounced "try", from retrieval) is a tree-like data structure designed for fast string lookups. Unlike a hash set that stores complete words, a Trie breaks each word into individual characters and stores them along a path from root to leaf.

The power of a Trie comes from shared prefixes. Words that start with the same characters share the same nodes at the top of the tree, branching off only where they differ.

The TrieNode

Every node in a Trie has three properties:

• c - The character this node represents
• isWordBoundary - A flag that marks whether a complete word ends here
• children - A HashMap mapping characters to child TrieNodes

The isWordBoundary flag is what separates a Trie from a simple tree. Without it, you'd have no way to tell whether a path represents an actual stored word or just a prefix of a longer word.

Understanding the Problem

We're given a partially implemented Trie class with a working search method and an empty insert method. Our job is to implement insert so that words can be added to the Trie and later found via search.

Here's the expected behavior after inserting three words:

trie.insert("FIRE")
trie.insert("FIRECODE")
trie.insert("FIRESIDE")

trie.search("FIRE")     -> true
trie.search("FIRECODE") -> true
trie.search("FIRESIDE") -> true
trie.search("FIRES")    -> false
trie.search("FIRECO")   -> false

Notice the last two results. "FIRES" returns false because even though an 'S' node exists under 'E' (as part of "FIRESIDE"), the 'S' node itself is not marked as a word boundary. "FIRECO" returns false for the same reason: the 'O' in "FIRECODE" is not a word boundary.

The Complete Trie

After all three insertions, the Trie looks like this:

The nodes marked with an asterisk (*) are word boundaries. Every path from the root to a word boundary node spells out one of our stored words. The shared prefix F-I-R-E is stored only once, and the tree branches at 'E' into two separate suffixes: CODE and SIDE.

Solution Approach

The insertion algorithm is surprisingly straightforward once you understand the structure. Think of it as walking down a hallway of doors:

1. Start at the root (the entrance)
2. For each character in the word, check if there's already a door labeled with that character
3. If the door exists, walk through it
4. If it doesn't, build a new door and walk through it
5. When you've placed the last character, hang a sign on the door that says "a word ends here"

Step-by-Step: Inserting "FIRE"

Let's trace through inserting the word "FIRE" into an empty Trie.

Character 'F': The root has no children. Create a new node for 'F' and move to it.

Character 'I': Node 'F' has no children. Create a new node for 'I' and move to it.

Character 'R': Node 'I' has no children. Create a new node for 'R' and move to it.

Character 'E': Node 'R' has no children. Create a new node for 'E', move to it, and mark it as a word boundary since 'E' is the last character.

When we later insert "FIRECODE", we'll traverse the existing F-I-R-E path without creating any new nodes, then create new nodes for C-O-D-E.

Implementation

Prefer a different language? Jump to solutions in other languages.

public void insert(String word) {
    // Start at the root of the Trie
    TrieNode node = root;

    // Walk through each character in the word
    for (int i = 0; i < word.length(); i++) {
        char c = word.charAt(i);

        // If no child exists for this character, create one
        if (!node.children.containsKey(c)) {
            node.children.put(c, new TrieNode(c));
        }

        // Move down to the child node
        node = node.children.get(c);

        // Mark the last character as a word boundary
        if (i == word.length() - 1) {
            node.isWordBoundary = true;
        }
    }
}

The algorithm processes each character exactly once. For every character, we do a constant-time hash map lookup (containsKey), potentially a constant-time insertion (put), and a constant-time traversal (get). When we reach the final character, we flip the isWordBoundary flag.

How Search Uses Word Boundaries

The provided search method follows the same traversal logic but instead of creating nodes, it returns false if a character is missing from the children map. At the end of the traversal, it returns node.isWordBoundary rather than true. This is the critical detail: a path might exist in the Trie, but if the final node isn't a word boundary, the word was never inserted.

Here's what happens when searching for "FIRES":

The search follows F-I-R-E successfully (green path). It then looks for 'S' in E's children and finds it (because "FIRESIDE" was inserted). But 'S' is not marked as a word boundary, so search("FIRES") returns false.

Complexity Analysis

Time Complexity: O(k)

Each insertion processes every character in the word exactly once. At each character, the hash map operations (containsKey, put, get) are O(1) on average. So the total time for inserting a word of length k is O(k).

This is a significant improvement over searching through a flat list of words, where finding a match takes O(n * k) for n words of average length k.

Space Complexity: O(n * k)

In the worst case, every word is completely unique with no shared prefixes, so we create a new node for every character of every word. That gives us O(n * k) total nodes where n is the number of words and k is the average word length.

In practice, Tries are much more space-efficient when words share common prefixes. Our example stores three words totaling 20 characters but only uses 14 nodes because the shared prefix "FIRE" is stored once.

Common Pitfalls

1. Forgetting the word boundary: The most common mistake. If you don't mark isWordBoundary = true at the end of the word, search will return false for every word. The nodes will exist, but the Trie won't know any words were stored.

2. Marking every node as a word boundary: The opposite mistake. If you set isWordBoundary = true on every node during insertion, then search("FIR") would return true even though only "FIRE" was inserted.

3. Creating nodes that already exist: Always check containsKey before creating a new node. If you skip this check and overwrite existing children, you'll lose entire branches of the Trie.

4. Off-by-one on the last character check: Using i == word.length() instead of i == word.length() - 1 means you never mark the word boundary. Alternatively, you can simplify by moving the boundary assignment after the loop: node.isWordBoundary = true.

Interview Tips

When you encounter this problem in an interview:

1. Clarify the character set: Ask whether inputs are lowercase, uppercase, or mixed. This affects whether you might use an array of size 26 instead of a HashMap for children. In this problem, all characters are uppercase.

2. Draw the Trie: Sketch a small example on the whiteboard. Inserting "CAT" and "CAR" makes the shared prefix and branching immediately visible.

3. Mention the tradeoff: Tries use more memory than hash sets but support prefix operations that hash sets cannot. This shows you understand when to choose each data structure.

4. Know the follow-ups: Be ready for "How would you implement autocomplete?" (DFS from the prefix endpoint), "How would you delete a word?" (traverse to the end, unmark the boundary, prune empty branches), and "How would you find the longest common prefix?" (traverse until a node has more than one child).

Real-World Applications

Tries power more systems than most engineers realize:

• Autocomplete: Google Search, IDE code completion, and phone keyboards all use Trie variants to suggest words as you type
• Spell checkers: Checking whether a word exists in a dictionary is a single Trie traversal
• IP routing: Routers use a specialized Trie (radix tree) to match IP addresses to network routes
• DNA sequence matching: Bioinformatics tools use suffix Tries to find patterns in genetic data
• T9 predictive text: The classic phone keyboard mapped key sequences to Trie paths

Solutions in Other Languages

Python

def insert(self, word):
    node = self.root
    for i in range(len(word)):
        c = word[i]
        if c not in node.children:
            node.children[c] = TrieNode(c)
        node = node.children[c]
        if i == len(word) - 1:
            node.is_word_boundary = True

Python's dictionary provides the same hash map semantics as Java's HashMap. The in operator checks for key existence, and assignment creates or overwrites entries.

JavaScript

insert(word) {
    let node = this.root;
    for (let i = 0; i < word.length; i++) {
        const c = word[i];
        if (!node.children.has(c)) {
            node.children.set(c, new TrieNode(c));
        }
        node = node.children.get(c);
        if (i === word.length - 1) node.isWordBoundary = true;
    }
}

JavaScript uses a Map for the children instead of a plain object, which provides cleaner semantics with has, set, and get.

TypeScript

insertWord(word: string): void {
    let node = this.trie.root;
    for (let i = 0; i < word.length; i++) {
        const c = word[i];
        if (!node.children.has(c)) {
            node.children.set(c, new TrieNode());
        }
        node = node.children.get(c)!;
        if (i === word.length - 1) node.isWord = true;
    }
}

The TypeScript version uses the non-null assertion operator (!) after get since we've guaranteed the key exists by the has check above it.

C++

void insert(string word) {
    TrieNode* node = root;
    for (int i = 0; i < word.length(); i++) {
        char c = word[i];
        if (node->children.find(c) == node->children.end()) {
            node->children[c] = new TrieNode(c);
        }
        node = node->children[c];
        if (i == word.length() - 1) {
            node->isWordBoundary = true;
        }
    }
}

C++ uses std::map with find for lookup. Note the -> operator for accessing members through pointers, and manual memory management with new.

Go

func (t *Trie) insert(word string) {
    node := t.root
    runes := []rune(word)
    for i, c := range runes {
        if _, exists := node.children[c]; !exists {
            node.children[c] = newTrieNode(c)
        }
        node = node.children[c]
        if i == len(runes)-1 {
            node.isWordBoundary = true
        }
    }
}

Go converts the string to a rune slice to handle characters properly. The idiomatic _, exists pattern checks map membership.

Scala

def insert(word: String): Unit = {
    var node = root
    for (i <- 0 until word.length) {
        val c = word.charAt(i)
        node = node.children.getOrElseUpdate(c, new TrieNode(c))
        if (i == word.length - 1) node.isWordBoundary = true
    }
}

Scala's getOrElseUpdate elegantly combines the "check and create" step into a single call, making the insertion body more compact.

Kotlin

fun insert(word: String) {
    var node = root
    for (i in 0 until word.length) {
        val c = word[i]
        if (!node.children.containsKey(c)) {
            node.children[c] = TrieNode(c)
        }
        node = node.children[c]!!
        if (i == word.length - 1) {
            node.isWordBoundary = true
        }
    }
}

Kotlin uses the !! operator to assert non-null after the containsKey check, similar to TypeScript's !.

Swift

func insert(_ word: String) {
    var node = root
    let chars = Array(word)
    for i in 0..<chars.count {
        let c = chars[i]
        if node.children[c] == nil {
            node.children[c] = TrieNode(c)
        }
        node = node.children[c]!
        if i == chars.count - 1 {
            node.isWordBoundary = true
        }
    }
}

Swift converts the string to a character array for indexed access. Dictionary subscript returns an optional, so we force-unwrap with ! after confirming the key exists.

Ruby

def insert(word)
    node = @root
    word.each_char.with_index do |c, i|
        if node.children.key?(c)
            node = node.children[c]
        else
            node.children[c] = TrieNode.new(c)
            node = node.children[c]
        end
        node.is_word_boundary = true if i == word.length - 1
    end
end

Ruby uses each_char.with_index for idiomatic character iteration. The key? method checks hash membership, and the trailing if keeps the boundary assignment on one line.

Rust

fn insert(&mut self, word: &str) {
    let mut node = &mut self.root;
    for (i, c) in word.chars().enumerate() {
        if !node.children.contains_key(&c) {
            node.children.insert(c, TrieNode::new(Some(c)));
        }
        node = node.children.get_mut(&c).unwrap();
        if i == word.len() - 1 {
            node.is_word_boundary = true;
        }
    }
}

Rust's ownership system requires &mut self for insertion and get_mut to obtain a mutable reference to the child. The unwrap is safe here because we just ensured the key exists.

C#

public void InsertWord(string word) {
    var node = trie.root;
    for (int i = 0; i < word.Length; i++) {
        char c = word[i];
        if (!node.children.ContainsKey(c)) {
            node.children[c] = new TrieNode();
        }
        node = node.children[c];
        if (i == word.Length - 1) {
            node.isWord = true;
        }
    }
}

C# uses Dictionary for the children map. The ContainsKey method and indexer syntax are idiomatic for checking and accessing entries.

Dart

void insert(String word) {
    TrieNode node = root;
    for (int i = 0; i < word.length; i++) {
        String c = word[i];
        if (!node.children.containsKey(c)) {
            node.children[c] = TrieNode(c);
        }
        node = node.children[c]!;
        if (i == word.length - 1) {
            node.isWordBoundary = true;
        }
    }
}

Dart's Map works similarly to Java's HashMap. The ! operator asserts non-null on the map lookup, and containsKey checks for existing children.

PHP

public function insert(string $word): void {
    $node = $this->root;
    $chars = str_split($word);
    for ($i = 0; $i < count($chars); $i++) {
        $char = $chars[$i];
        if (!isset($node->children[$char])) {
            $node->children[$char] = new TrieNode($char);
        }
        $node = $node->children[$char];
        if ($i === count($chars) - 1) {
            $node->isWordBoundary = true;
        }
    }
}

PHP uses str_split to convert the string into an array of characters and isset to check whether a key exists in the associative array.

Related Problems

Once you've mastered basic Trie insertion, build on that foundation with these problems:

• Implement Trie search and prefix checking
• Word search in a 2D grid using a Trie
• Design an autocomplete system
• Longest word in a dictionary

These problems all build on the same traversal pattern you've learned here. The difference is what you do at each node.

This problem and hundreds of others are available on Firecode, where over 50,000 engineers have prepared for technical interviews at top companies. The spaced repetition system helps you internalize patterns like Trie traversal so they become second nature when it counts.