Trie Data Structure: Introduction

What Is a Trie?

A Trie, also called a prefix tree or prefix trie, is a tree-based data structure designed primarily for storing and searching strings. Unlike a Binary Search Tree or a hash table, a Trie organizes data according to the individual characters that make up each string.

The structure makes Trie particularly useful when an application needs to work with prefixes. Common examples include autocomplete, dictionary lookup, spell checking, search suggestions, and word filtering.

Words:

cat
car
care
dog

Trie:

(root)
├── c
│   └── a
│       ├── t *
│       └── r *
│           └── e *
└── d
    └── o
        └── g *

The shared characters are stored along common paths. For example, cat, car, and care share the prefix ca.

Why Is It Called a Prefix Tree?

A prefix is the beginning portion of a string. For example, the prefixes of care include c, ca, car, and care.

A Trie represents these prefixes as paths from the root. Every character along a path contributes to the prefix represented by that path.

          root
            |
            c
            |
            a
            |
            r
            |
            e

Path: c → a → r → e
Word: care
Prefixes: c, ca, car, care

How a Trie Stores Words

A Trie begins with a root node that usually does not represent a character. Each outgoing edge or child relationship represents a character.

When a word is inserted, the Trie follows the characters one by one. Existing nodes are reused when the corresponding character is already present. New nodes are created only when necessary.

Insert: "car"

(root)
  |
  c
  |
  a
  |
  r


Insert: "cat"

(root)
  |
  c
  |
  a
 / \
r   t

The characters c and a are shared because both words have the same prefix.

Trie Node Structure

A Trie node normally stores references to its child nodes and an indicator showing whether the node represents the end of a complete word.

TrieNode
├── children
└── isEndOfWord

The isEndOfWord flag is important because one word can be a prefix of another. For example, if both car and care are stored, the node representing r must indicate that car is already a complete word.

car
 |
 c → a → r *
             \
              e *

* = end of a stored word

Trie Example With Multiple Words

Suppose we insert the following words:

app
apple
apply
bat
bath

A simplified representation looks like this:

(root)
├── a
│   └── p
│       └── p *
│           ├── l
│           │   └── e *
│           └── l
│               └── y *
└── b
    └── a
        └── t *
            └── h *

Notice how app, apple, and apply share the path representing app.

Trie Search

Searching for a word in a Trie means following one character at a time from the root. If every character exists and the final node is marked as the end of a word, the word exists in the Trie.

Search: "apple"

(root)
  |
  a
  |
  p
  |
  p
  |
  l
  |
  e *

All characters found
Final node is marked as a word
Result: Found

Finding a prefix does not automatically mean that the complete word exists. For example, if apple is stored, the prefix app may exist even if it was not inserted as a complete word. The end-of-word marker distinguishes these cases.

Trie and Prefix Searching

Prefix searching is one of the main reasons to use a Trie. Once the node representing a prefix is found, all words below that node share the same prefix.

Stored words:

car
card
care
careful
cat
dog

Prefix: "car"

        c
        |
        a
        |
        r
       /|\
      d e

Possible results:
car
card
care
careful

Trie vs Array

An array stores values in positions, while a Trie organizes characters into paths. An array is usually a better fit for indexed collections, whereas a Trie is designed around string prefixes.

Trie vs Hash Table

Hash tables are excellent for exact key lookup, but they do not naturally expose the relationship between keys that share a prefix. A Trie explicitly represents that relationship.

Trie Time Complexity

Let L represent the length of a word or prefix. Basic Trie operations process characters one at a time, so their running time is generally proportional to the number of characters being processed.

The actual memory usage depends heavily on how children are represented. For example, an implementation using a fixed array for every possible character can consume considerably more memory than one using a map of only the children that actually exist.

Simple Trie Implementation in JavaScript

JavaScript can represent a Trie node using a Map. The map stores only the characters that actually occur as children.

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

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

Inserting a Word

During insertion, the Trie processes each character from left to right. If a child for the current character does not exist, a new node is created.

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.isEndOfWord = true;
}

Searching for a Word

Search follows the same character path used during insertion. The important difference is that the final node must have isEndOfWord set to 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.isEndOfWord;
}

Checking a Prefix

A prefix check only needs to determine whether the character path exists. It does not require the final node to represent a complete word.

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;
}

Where Tries Are Used

Tries are especially useful in applications where strings need to be searched by their prefixes or where large collections of words share common beginnings.

• Autocomplete and search suggestions.
• Dictionary implementations.
• Spell checking and word validation.
• Prefix-based search.
• Contact and username search.
• Search filtering.
• Word games and puzzle applications.
• IP address and routing-related prefix matching in specialized Trie variants.

Advantages of a Trie

• Efficient word and prefix operations based on string length.
• Prefixes are represented explicitly in the data structure.
• Words with common prefixes can share nodes.
• Autocomplete can be built naturally on top of the structure.
• Search performance does not depend directly on the number of stored words for basic traversal.

Limitations of a Trie

• Memory usage can become significant for large dictionaries.
• Child representation affects memory efficiency.
• Tries are more specialized than general-purpose collections.
• Additional logic is required to collect all words below a prefix.
• Implementation becomes more complex when supporting Unicode, case normalization, or specialized alphabets.

Trie vs Binary Search Tree

Both Tries and Binary Search Trees can store strings, but they organize those strings differently. A BST compares complete values to decide whether to move left or right. A Trie follows individual characters.

BST:
Compare complete strings
        ↓
   left or right
        ↓
Compare again


Trie:
Compare character
        ↓
Follow character child
        ↓
Compare next character
        ↓
Continue along prefix

This difference makes Tries particularly useful when the operation itself is based on prefixes rather than only exact values.

Common Mistakes

• Forgetting that the root normally does not represent a character.
• Assuming every node represents a complete word.
• Not storing an end-of-word marker.
• Confusing a prefix with a complete stored word.
• Assuming Trie search automatically returns all matching words for a prefix.
• Using large fixed child arrays without considering memory requirements.
• Assuming a Trie is always more memory-efficient than a hash table.

Key Takeaways

• A Trie is a tree-based data structure designed primarily for strings.
• It is also known as a prefix tree.
• Each path from the root represents a sequence of characters.
• Words with common prefixes can share the same nodes.
• An end-of-word marker distinguishes complete words from prefixes.
• Insertion, exact search, and prefix checks typically take O(L), where L is the string length.
• Tries are especially useful for autocomplete and prefix-based search.
• Memory usage depends strongly on how child nodes are represented.