Overview

A Trie—pronounced “try”—is a tree designed for strings. Each edge represents a character, and each root-to-node path represents a prefix. By sharing common prefixes, tries support autocomplete, dictionaries, spell checking, and contact search efficiently.

Key concepts

• Each path from the root represents a prefix
• Child links represent the next possible characters
• An end marker distinguishes a complete word from a prefix
• Operation time depends primarily on the string length

What is a Trie?

Unlike a Binary Search Tree node that stores a complete value, a Trie follows one character at a time. Words with the same beginning reuse the same path.

Storing Cat, Car, and Can produces the following shared Ca prefix.

        Root
          |
          C
          |
          A
       /  |        T*  R*  N*

The asterisks mark nodes where complete words end.

Why do we need a Trie?

To find every word beginning with App in an array, a program may need to examine every stored word. A Trie follows A → P → P directly; every complete word beneath that node has the required prefix.

Structure of a Trie Node

A node normally stores a collection of child links and a Boolean indicating whether a word ends at that node.

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

const root = new TrieNode();

Implementing a Trie in JavaScript

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

  insert(word) {
    let node = this.root;

    for (const character of word) {
      if (!node.children.has(character)) {
        node.children.set(character, new TrieNode());
      }
      node = node.children.get(character);
    }

    node.isEndOfWord = true;
  }

  search(word) {
    const node = this.findNode(word);
    return node !== null && node.isEndOfWord;
  }

  startsWith(prefix) {
    return this.findNode(prefix) !== null;
  }

  findNode(text) {
    let node = this.root;

    for (const character of text) {
      if (!node.children.has(character)) return null;
      node = node.children.get(character);
    }

    return node;
  }
}

Inserting a Word

• Start at the root
• Read the word one character at a time
• Create a child node when the character link is missing
• Move to that child
• Mark the final node as the end of a word

Inserting Dog creates the path Root → D → O → G*, where the final marker records that Dog is a complete word.

const trie = new Trie();

trie.insert("cat");
trie.insert("car");
trie.insert("can");

Searching for a Word

Exact search follows each character and then checks the end marker. This final check matters: after inserting car, searching for ca finds a valid prefix path but not a complete stored word.

console.log(trie.search("car")); // true
console.log(trie.search("ca"));  // false
console.log(trie.search("cap")); // false

Prefix Search

Prefix search succeeds as soon as every prefix character has been followed; it does not require an end marker.

console.log(trie.startsWith("ca")); // true
console.log(trie.startsWith("do")); // false

An autocomplete system can locate the App node and traverse the subtree below it to collect Apple, Application, Apply, Appointment, and other matching words.

Deleting a Word

Deletion first clears the word's end marker. Nodes can then be removed from the bottom upward only while they have no children and do not end another word. Shared prefix nodes must remain available for other words.

Time complexity

Here, m is the number of characters in the input string. Returning every autocomplete match also requires time proportional to the matching subtree and output size.

Trie vs Hash Map

Advantages of a Trie

• Fast exact-word lookup
• Efficient prefix matching
• Natural autocomplete traversal
• Stores shared prefixes once
• Performance does not require scanning every stored word

Limitations of a Trie

• Node and child containers can consume substantial memory
• Implementation is more complex than a set or map
• Large alphabets increase branching and storage
• The structure is specialized for sequence and string keys

Real-life applications

• Search autocomplete
• Mobile keyboard suggestions
• Spell checking
• Contact search
• Dictionaries
• URL routing
• Word games
• Predictive text

Tips for beginners

• Understand basic trees first
• Trace one character per edge
• Distinguish a prefix from a complete word
• Practice insert, search, and startsWith
• Draw shared prefixes
• Build a small autocomplete feature

Key takeaways

• A Trie is a prefix tree for strings
• Paths represent prefixes
• End markers identify complete words
• Common prefixes share storage
• Core operations take O(m)
• Tries trade additional memory for efficient prefix operations
• Autocomplete, dictionaries, and contact search are natural Trie applications