If you've ever used a search bar that suggests completions as you type, you've interacted with a Trie (pronounced "try," coming from "retrieval"). While a HashMap is great for exact matches, it's useless for prefix searches. If you want to find every word that starts with "Java," a HashMap would force you to iterate through every single key. A Trie, however, organizes data in a tree where each node represents a single character. It's essentially a roadmap of prefixes.

Defining the building block

First, we need a TrieNode. I usually prefer using a HashMap for the children instead of a fixed-size array. Sure, an array of 26 characters is slightly faster for lowercase English, but the Map allows us to handle any Unicode character without wasting memory on empty slots.

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isEndOfWord = false;
}

Keep it simple. Each node just needs to know who its children are and whether it marks the final character of a complete word.

Wiring up the insertion logic

Now, let's build the actual Trie. We'll start with a basic insert method. The logic here is straightforward: start at the root, and for every character in the word, check if a child node exists. If it doesn't, create one. Then, move your pointer to that child and repeat.

public class LanguageTrie {
    private final TrieNode root = new TrieNode();

    public void insert(String word) {
        TrieNode current = root;
        for (char c : word.toCharArray()) {
            current = current.children.computeIfAbsent(c, k -> new TrieNode());
        }
        // We'll get back to this line in a second
    }
}

The "Invisible Word" mistake

I'll be honest: when I first started implementing Tries, I always forgot the most important line in the insert method. I'd write the loop, successfully build the path of nodes, and then... nothing. When I tried to search for the word, the Trie would tell me it didn't exist, even though the characters were all there.

The problem is that without marking the end of the word, the Trie can't distinguish between a word and a prefix. If I insert "JavaScript", the nodes for "Java" are created automatically. If I then search for "Java", the Trie sees the path exists, but it doesn't know if "Java" was actually intended to be a word or if it's just the start of "JavaScript".

Here is the fix. We must explicitly mark the final node:

public void insert(String word) {
    TrieNode current = root;
    for (char c : word.toCharArray()) {
        current = current.children.computeIfAbsent(c, k -> new TrieNode());
    }
    current.isEndOfWord = true; // This is the crucial bit!
}

Implementing the prefix search

The real power of the Trie is the startsWith method. This is what powers autocomplete. We just traverse the tree based on the prefix. If we hit a null child before we finish the prefix, we know no words start with that sequence.

public boolean startsWith(String prefix) {
    TrieNode current = root;
    for (char c : prefix.toCharArray()) {
        TrieNode node = current.children.get(c);
        if (node == null) {
            return false;
        }
        current = node;
    }
    return true;
}

Now we have a system where we can instantly verify if any language in our dataset starts with a specific string, regardless of how many millions of words we've stored. The time complexity is O(L), where L is the length of the prefix, making it incredibly efficient.

📋 Practical Task

Feature Extension: Building a "Find All Suggestions" Method

Your current Trie can tell you if a prefix exists, but it can't give you the actual words. Your task is to add a method to the LanguageTrie class called getSuggestions(String prefix).

The method should:

• Return a List<String> of all words in the Trie that begin with the given prefix.
• Navigate to the node representing the end of the prefix.
• Use a recursive helper method (Depth-First Search) to traverse all possible paths from that node downward to find every node marked as isEndOfWord.