I've noticed a recurring trend when developers first encounter the Trie (or prefix tree). They tend to look at it and think, "Why bother? I can just use a Set or a Map to store my strings. Looking up a key in a Map is O(1); why would I want to manually traverse a tree of characters?"

A Trie is just a fancy Hash Map

On the surface, if your only goal is to check if a word exists in a list, a Set is indeed faster and simpler. But the "Hash Map mentality" falls apart the moment you need to do anything related to prefixes.

Imagine you're building a search bar that suggests words. You have 100,000 words in your dictionary, and the user types "app". If you're using a Set, you have to iterate through every single one of those 100,000 strings and check if word.startsWith('app'). That's an O(N * L) operation, where N is the number of words and L is the average length. It's sluggish and wasteful.

In a Trie, however, you don't search the list; you follow a path. You go to the 'a' node, then the 'p' node, then the next 'p' node. Once you arrive at that second 'p', you are already standing at the root of every single word in your dictionary that starts with "app". You've ignored 99% of your data in three steps. That's the power of the Trie: it turns a global search into a targeted traversal.

Building the DNA of the Tree

To implement this in JavaScript, we don't actually store the strings themselves in the nodes. Instead, the "value" of a node is implied by its position in the tree. Each node just needs to know two things: who its children are, and whether it represents the completion of a valid word.

class TrieNode {
  constructor() {
    // We use an object to map characters to their corresponding child nodes
    this.children = {}; 
    this.isEndOfWord = false;
  }
}

I prefer using a plain JavaScript object for children here because it's concise, though a Map would work just as well if you expect keys that aren't strings (which isn't the case for a Trie).

Walking the Path to a Word

Now we need the actual Trie class to manage these nodes. The core logic for both inserting and searching is almost identical: you loop through the characters of your string and move deeper into the tree.

When inserting, if a character doesn't exist as a child, you create a new node. When searching, if a character doesn't exist, you can stop immediately—the word isn't there. I'll show you the implementation below. Pay close attention to how isEndOfWord is used; without it, you couldn't tell the difference between the word "app" and the word "apple" if both were stored.

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  insert(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children[char]) {
        node.children[char] = new TrieNode();
      }
      node = node.children[char];
    }
    node.isEndOfWord = true;
  }

  search(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children[char]) return false;
      node = node.children[char];
    }
    return node.isEndOfWord;
  }

  startsWith(prefix) {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children[char]) return false;
      node = node.children[char];
    }
    // Unlike search(), we don't care if isEndOfWord is true.
    // If we reached this point, the prefix exists.
    return true;
  }
}

The startsWith method is where the Trie really earns its keep. It's the foundation for autocomplete, spell-checkers, and IP routing tables. You're essentially navigating a roadmap where every intersection is a character.

📋 Practical Task

Build a Predictive Text Suggestion Engine

Using the Trie and TrieNode implementations from the lesson, extend the functionality to create a predictive text engine. Your task is to implement a method called getSuggestions(prefix) inside the Trie class.

Requirements:

• The getSuggestions method should take a string (the prefix) and return an array of all words in the Trie that begin with that prefix.
• You will need to use a helper function (likely recursive) to perform a Depth-First Search (DFS) starting from the end of the prefix path to find all descendant nodes marked as isEndOfWord.
• Test your implementation by inserting the words: "apple", "app", "application", "ball", "bat", "batch". Calling getSuggestions("app") should return ["app", "apple", "application"].