Stop Searching Word by Word. Understand the Trie Data Structure

A beginner-friendly guide to how prefix trees store words, share characters, and make searching easier.

Stop Searching Word by Word. Understand the Trie Data Structure

Imagine you have 10,000 words stored in your application. A user types care, and you need to check whether that word exists.

How would you do it?

You could store all the words in an array and check them one by one. You could use a Set or a Map for quick lookups. But what if your application also needs to suggest words while the user is typing?

For example, when someone types ca, you want to suggest cat, car, care, and can.

Now the problem becomes a little more interesting.

Instead of treating every word as a separate item, what if we could reuse the characters that multiple words have in common?

That is where the Trie data structure comes in.

Let’s understand how it works, why it is useful, and how to implement one in JavaScript.

1. What Is a Trie?

A Trie (pronounced like “try”) is a tree-based data structure used to store and search sequences of characters.

It is also called a prefix tree because words with the same prefix share the same path in the tree.

Let’s say we want to store these five words:

  • cat

  • car

  • care

  • can

  • happy

If we store every word separately, we repeat some characters. For example, cat, car, and care all start with ca.

A Trie allows us to share those characters.

It looks something like this:

root
 ├── c
 │   └── a
 │       ├── t*      cat
 │       ├── r*      car
 │       │   └── e*  care
 │       └── n*      can
 │
 └── h
     └── a
         └── p
             └── p
                 └── y*  happy

The * indicates the end of a complete word.

Notice something interesting.

The words cat, car, care, and can all share the same path:

root → c → a

We create separate branches only when the characters become different.

This is the basic idea behind a Trie.

Each node represents a character, and its children represent the characters that can follow it.

But there is one important detail we need to understand before writing code.

2. Why Do We Need an End-of-Word Marker?

Look at these three words:

car
care
careful

They all share the prefix car.

Now suppose we insert careful into a Trie.

Does that automatically mean care exists in our collection? No.

A path can exist in a Trie without representing a complete word.

For example, if we store only careful, the path for care exists, but we haven't necessarily stored care as a complete word.

That is why we need an additional property, usually called isWord or isEnd.

For example:

c → a → r → e
            ↑
         isWord = true

If the node for e has isWord = true, we know that care is a complete word.

If the node exists but isWord = false, it means the characters form a prefix of another word.

This small detail is essential. Without it, our search function could return incorrect results.

Now that we understand the structure, let’s build one.

3. Building a Trie in JavaScript

We’ll create two classes:

  1. TrieNode to represent each node.

  2. Trie to manage insertion and searching.

Step 1: Create a TrieNode

First, let’s define what each node should contain.

class TrieNode {
  constructor() {
    this.children = new Map();
    this.isWord = false;
  }
}

There are only two properties here. children

This is a Map that stores the child nodes.

For example, if a node represents c, its children might contain an entry for a.

We use a Map because we only need to store the characters that actually exist as children. We don't need to allocate space for every possible character.

isWord

This tells us whether the current node marks the end of a complete word.

Initially, it is false because a newly created node doesn't represent a complete word yet.

That’s all we need for a basic Trie node.

Step 2: Create the Trie class

Now let’s create the Trie itself.

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

The root is the starting point of our tree.

It doesn’t represent a character. Instead, it acts as the entry point from which we follow the characters of a word.

For example, to find cat, we start at the root and follow the links for c, a, and t.

Let’s see how we can create those links.

4. How Does Insertion Work?

Suppose we want to insert the word cat.

We start at the root and process one character at a time.

Insert "cat"
root → c → a → t*

Here’s what happens:

  1. Check whether the root has a child for c.

  2. If it doesn’t, create a new node for c.

  3. Move to the c node and look for a.

  4. Create the a node if necessary.

  5. Continue until we reach t.

  6. Mark the t node as the end of a complete word.

Now let’s insert car.

Before inserting "car":
root → c → a → t*
After inserting "car":
root → c → a
             ├── t*
             └── r*

Notice that we didn’t create another c or a node.

We reused the existing path and created only the new branch for r.

This is how a Trie shares common prefixes.

Let’s translate this process into JavaScript.

class Trie {
  constructor() {
    this.root = new TrieNode();
  }
  insert(word) {
    let current = this.root;
    for (const char of word) {
      if (!current.children.has(char)) {
        current.children.set(char, new TrieNode());
      }
      current = current.children.get(char);
    }
    current.isWord = true;
  }
}

Let’s understand the important lines.

let current = this.root;

We start from the root. The current variable helps us move through the tree without changing the root itself.

Next:

for (const char of word) {

We process each character in the word.

For cat, the characters are c, a, and t.

Then:

if (!current.children.has(char)) {
  current.children.set(char, new TrieNode());
}

If the required child doesn’t exist, we create it.

If it already exists, we reuse it. This is what allows multiple words to share the same prefix.

Finally:

current = current.children.get(char);

We move to the next node and continue processing the word.

Once the loop finishes, we’ve reached the last character. We mark that node as the end of a complete word:

current.isWord = true;

And that’s it. We’ve implemented insertion.

But how do we check whether a word exists?

5. How Does Searching Work?

The search operation is very similar to insertion.

Suppose our Trie contains:

cat
car
care
can

Now let’s search for car.

We start at the root and follow the path:

root → c → a → r

If every character exists and the final node has isWord = true, the word exists in the Trie.

What happens if we search for cap?

We can follow c and a, but there is no child for p under the a node.

So we return false.

Now consider searching for ca.

The path exists, but if we haven’t inserted ca as a complete word, its final node won't have isWord = true.

We must return false in that case, too.

Here’s the implementation:

search(word) {
  let current = this.root;
 for (const char of word) {
    if (!current.children.has(char)) {
      return false;
    }
    current = current.children.get(char);
  }
  return current.isWord;
}

The last line is especially important:

return current.isWord;

We don’t simply return true because the path exists. We check whether the final node marks a complete word.

Let’s put everything together and test it.

6. Complete Trie Implementation

class TrieNode {
  constructor() {
    this.children = new Map();
    this.isWord = false;
  }
}
class Trie {
  constructor() {
    this.root = new TrieNode();
  }
  insert(word) {
    let current = this.root;
    for (const char of word) {
      if (!current.children.has(char)) {
        current.children.set(char, new TrieNode());
      }
      current = current.children.get(char);
    }
    current.isWord = true;
  }
  search(word) {
    let current = this.root;
    for (const char of word) {
      if (!current.children.has(char)) {
        return false;
      }
      current = current.children.get(char);
    }
    return current.isWord;
  }
  startsWith(prefix) {
    let current = this.root;
    for (const char of prefix) {
      if (!current.children.has(char)) {
        return false;
      }
      current = current.children.get(char);
    }
    return true;
  }
}
const trie = new Trie();
trie.insert("cat");
trie.insert("car");
trie.insert("care");
trie.insert("can");
trie.insert("happy");
console.log(trie.search("cat"));  // true
console.log(trie.search("care")); // true
console.log(trie.search("cap"));  // false
console.log(trie.search("ca"));   // false
console.log(trie.startsWith("ca")); // true
console.log(trie.startsWith("hap")); // true
console.log(trie.startsWith("xyz")); // false

We also added a startsWith() method.

Did you notice how similar it is to search()?

The main difference is the return condition.

  • search() checks whether the final node represents a complete word.

  • startsWith() checks whether the requested prefix exists as a path.

For example, ca is a valid prefix of cat, car, care, and can. Even if ca isn't a complete word in our collection, startsWith("ca") returns true.

This difference is one of the reasons Tries are useful for prefix-based operations.

7. Time Complexity: Is Searching Really O(1)?

Let’s talk about complexity, because this is where things get interesting.

Suppose you insert the word care.

It has four characters.

  • During insertion, we process c, a, r, and e. During searching, we follow the same four character links.

  • If the word has (L) characters, insertion and search take (O(L)) time, assuming child lookups are constant-time on average.

Operation and its time complexity

Here, (L) represents the word length and (P) represents the prefix length.

Notice that the time complexity depends on the length of the word, not directly on how many words are stored.

Whether the Trie contains 100 words or 10,000 words, searching for a word of the same length requires following at most that many character links.

Of course, the larger Trie generally requires more memory, and its performance in a real application also depends on the implementation and the data.

What about space complexity?

A Trie creates nodes for the character paths it needs.

If several words share prefixes, those prefixes can reuse nodes. If the words have very few common characters, the Trie may need many more nodes.

So the total space depends on the number of distinct prefixes and the way child references are stored.

In our JavaScript implementation, every node has a Map, which has its own memory overhead. That's a trade-off worth remembering.

8. Where Are Tries Useful in Real Applications?

Let’s return to the autocomplete problem from the beginning.

Imagine you’re building a search box. Your word collection contains:

cat
car
care
can
happy

When a user types ca, you want to suggest words that start with those characters.

A Trie can help you do that.

First, follow the path for c, then a. Once you reach the node for ca, you can explore its descendants to find words such as cat, car, care, and can.

This is where the prefix-based structure becomes useful.

Some common applications include:

  • Autocomplete: Suggesting words while a user types.

  • Dictionary lookup: Checking whether a word exists.

  • Prefix search: Finding words that start with a given sequence of characters.

  • Word games: Finding words that match particular prefixes.

  • Routing and text processing: Organizing sequences of symbols for specialized lookup tasks.

One important point: not every autocomplete system uses a Trie. Real applications may combine several data structures, ranking systems, caches, and other techniques depending on their requirements.

Can we print all words stored in a Trie?

Yes. We can use Depth-First Search (DFS) to traverse the tree.

Whenever we reach a node marked as a complete word, we can print the characters we’ve collected along the path.

If we visit child characters in sorted order, we can also print the stored words in lexicographical order, subject to the character ordering we choose.

This is another useful property of organizing words by their prefixes.

9. Trie vs. HashMap vs. Set

You might be wondering: if JavaScript already has Map and Set, why do we need another data structure?

The answer depends on the problem we’re trying to solve.

A Set is useful when you want to check whether a complete value exists. A Map is useful when you want to associate a key with a value.

A Trie organizes strings character by character, which makes prefix operations natural.

For example:

  • If you only need to check whether care exists, a Set may be simpler.

  • If you need to find all words starting with ca, a Trie provides a natural way to navigate to that prefix and explore the matching branches.

  • If you need autocomplete suggestions ranked by popularity or relevance, a Trie might be one component of a larger solution.

The lesson isn’t that Tries are always better. It’s that the data structure should match the operations your application needs.

Conclusion: Understand the Problem Before Choosing the Data Structure

When I look at a data structure like a Trie, I don’t start by memorizing its implementation.

I start by asking a simple question: What problem does this structure make easier to solve?

For a Trie, the answer is organizing strings around their shared prefixes.

Once that idea becomes clear, the implementation feels much more natural. We start at the root, follow one character at a time, create missing nodes when inserting, and use an end-of-word marker to distinguish complete words from prefixes.

That’s the core of the data structure.

You don’t need to memorize every line of code. Understand why the nodes are connected the way they are, why the terminal marker exists, and when prefix-based operations are useful.

The next time you encounter a problem involving autocomplete, dictionaries, or prefix searches, you’ll have another tool to consider.

One question for you: Have you ever implemented a Trie in a coding interview, or have you mostly used arrays, Sets, and Maps? Share your experience in the comments.

From Tech By Neha Gupta

  • 👏 Enjoyed the article? Don’t forget to leave a clap.

  • 💬 Have thoughts or questions? Share them in the comments.