How to Implement a Trie Data Structure

Implementing a Trie

A Trie is built from nodes connected through character-based paths. A practical implementation needs to support creating nodes, inserting words, searching for complete words, and checking whether a prefix exists.

In JavaScript, a Map is a useful choice for storing a node's children because it stores only the characters that actually occur instead of allocating space for every possible character.

Trie Node Design

Each Trie node needs two main pieces of information:

• children stores references to child nodes indexed by characters.
• isEndOfWord indicates whether the node represents the end of a stored word.

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

The root node is also a Trie node, but it normally does not represent an actual character. It provides the starting point for every stored word.

Creating the Trie

The Trie itself needs a reference to its root node. All insertions and searches begin from this root.

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

At this point, the Trie is empty. The root exists, but it has no character children.

Inserting a Word

To insert a word, start at the root and process each character from left to right. For every character, check whether a corresponding child already exists.

If the child does not exist, create a new Trie node. Then move to that child and continue with the next character.

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

Tracing an Insertion

Suppose we insert the word cat.

Insert: "cat"

Step 1:
(root) → c

Step 2:
(root) → c → a

Step 3:
(root) → c → a → t

Mark t as the end of the word.

If car is inserted afterward, the existing c and a nodes are reused.

        root
          |
          c
          |
          a
         / \
        t   r
        *   *

* = complete word

Why the End-of-Word Flag Matters

Consider inserting car and care. The node representing r is both the end of car and a prefix of care.

c → a → r → e
        *
        |
        +── r is the end of "car"
        |
        +── e continues "care"

Without isEndOfWord, the implementation could tell that the character path exists but could not distinguish between a complete stored word and only a prefix.

Searching for a Word

Searching follows the same path used during insertion. If any character is missing, the word does not exist. If all characters are found, the final node must be marked as the end of a word.

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

Searching Step by Step

Suppose the Trie contains cat and car. Searching for cat follows the path:

root
 ↓
 c   found
 ↓
 a   found
 ↓
 t   found
 ↓
isEndOfWord = true

Result: true

Searching for can reaches ca, but there is no n child, so the search immediately returns false.

Checking Whether a Prefix Exists

A prefix search is slightly different from a complete-word search. The final node does not need to be marked as the end of a word. The implementation only needs to confirm that the complete prefix path exists.

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

For example, if apple is stored, app returns true even when app itself was never inserted as a complete word.

Complete Basic Trie Implementation

Combining the node, insertion, search, and prefix operations gives us a reusable Trie implementation.

class TrieNode {
  constructor() {
    this.children = new Map();
    this.isEndOfWord = 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.isEndOfWord = 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;
  }

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

Using the Trie

After creating a Trie instance, words can be inserted and then queried using the available operations.

const trie = new Trie();

trie.insert("apple");
trie.insert("application");
trie.insert("banana");

console.log(trie.search("apple"));
console.log(trie.search("app"));
console.log(trie.startsWith("app"));
console.log(trie.startsWith("ban"));

The expected results are:

true
false
true
true

Finding the Node for a Prefix

Prefix-based applications often need more than a boolean result. For example, an autocomplete system may need to find the node representing app and then explore all descendants to collect matching words.

A helper method can return the node reached after following a prefix.

findNode(prefix) {
  let current = this.root;

  for (const char of prefix) {
    if (!current.children.has(char)) {
      return null;
    }

    current = current.children.get(char);
  }

  return current;
}

Collecting Words From a Prefix

Once the node representing a prefix has been found, a depth-first traversal can explore its descendants and construct complete words.

collectWords(node, prefix, result) {
  if (node.isEndOfWord) {
    result.push(prefix);
  }

  for (const [char, child] of node.children) {
    this.collectWords(child, prefix + char, result);
  }
}

This technique forms the basis of many autocomplete implementations.

Deleting a Word

Deleting from a Trie is more involved than insertion or search because removing a word should not accidentally remove nodes that are still required by another word.

For example, if both car and care exist, deleting car should preserve the nodes needed for care.

car
 \
  e

Delete "car"

Keep:
c → a → r → e

Only change:
r.isEndOfWord = false

Nodes can be physically removed only when they are no longer part of another stored word. This is why Trie deletion commonly uses recursion or a bottom-up cleanup process.

Recursive Delete Implementation

A recursive deletion algorithm can first reach the end of the word and then remove unnecessary nodes while returning toward the root.

delete(word) {
  const remove = (node, index) => {
    if (index === word.length) {
      if (!node.isEndOfWord) {
        return false;
      }

      node.isEndOfWord = false;

      return node.children.size === 0;
    }

    const char = word[index];
    const child = node.children.get(char);

    if (!child) {
      return false;
    }

    const shouldDeleteChild = remove(child, index + 1);

    if (shouldDeleteChild) {
      node.children.delete(char);
    }

    return (
      node.children.size === 0 &&
      !node.isEndOfWord
    );
  };

  remove(this.root, 0);
}

Trie Operations and Complexity

If L is the length of the word or prefix being processed, the basic operations traverse at most one node for each character.

Choosing the Children Representation

The way child nodes are stored has a significant effect on Trie memory usage and lookup behavior.

Using Map

A Map stores only the characters that actually have children. This is flexible and works well when the character set is large or sparse.

this.children = new Map();

this.children.set("a", new TrieNode());
this.children.set("b", new TrieNode());

Using an Array

For a known and small alphabet, such as lowercase English letters, an array can provide direct character indexing. The trade-off is increased memory consumption because every node may allocate space for many possible characters.

class TrieNode {
  constructor() {
    this.children = new Array(26).fill(null);
    this.isEndOfWord = false;
  }
}

Case Sensitivity

Trie implementations need a consistent policy for character casing. Without normalization, Apple and apple are treated as different paths.

trie.insert("Apple");

trie.search("Apple"); // true
trie.search("apple"); // false

If an application should treat them as the same word, it can normalize input before insertion and search.

const normalizedWord = word.toLowerCase();

When to Use a Trie

A Trie is a good candidate when the application repeatedly works with strings and the relationship between prefixes matters.

• Autocomplete systems.
• Search suggestions.
• Dictionary and word lookup systems.
• Prefix filtering.
• Spell checking.
• Word games.
• Large collections of strings with shared prefixes.

Common Implementation Mistakes

• Forgetting to mark the final node as isEndOfWord.
• Returning true for a prefix when the caller asked for a complete word.
• Deleting shared nodes that are still required by another word.
• Using inconsistent case normalization.
• Creating a fixed-size child array without considering the alphabet and memory cost.
• Confusing prefix lookup with retrieving all matching words.
• Forgetting that the root normally represents no character.

Key Takeaways

• A Trie consists of character-based nodes connected from a root.
• Each node maintains its children and whether it terminates a complete word.
• Insertion creates missing character nodes and marks the final node.
• Search requires both a complete character path and an end-of-word marker.
• Prefix search only requires the character path to exist.
• Deletion must preserve nodes shared by other words.
• Map and arrays are common choices for representing children.
• Basic Trie operations generally take O(L), where L is the processed string length.