Trie

A generic trie (prefix tree) implementation that efficiently stores and retrieves strings with associated values. Perfect for autocomplete, spell checking, and prefix-based searches.

Installation

npm

npm install @msnkr/data-structures

pnpm

pnpm install @msnkr/data-structures

yarn

yarn add @msnkr/data-structures

Deno (JSR)

import { Trie } from 'jsr:@mskr/data-structures';

Browser (CDN)

<script type="module">
  import { Trie } from 'https://esm.sh/jsr/@mskr/data-structures';
</script>

Usage

import { Trie } from '@msnkr/data-structures';

const trie = new Trie<number>();

API Reference

Properties

• size: number - Number of words stored in the trie
• isEmpty(): boolean - Whether the trie is empty

Methods

Adding and Removing Words

// Insert word with associated value - O(m)
trie.insert('hello', 1);

// Remove word - O(m)
const removed = trie.remove('hello');

// Clear all words - O(1)
trie.clear();

where m is the length of the word

Searching and Retrieval

// Search for exact word - O(m)
const value = trie.search('hello');

// Check if word exists - O(m)
const exists = trie.contains('hello');

// Check if prefix exists - O(p)
const hasPrefix = trie.hasPrefix('hel');

// Get all words with prefix - O(p + n)
const words = trie.getAllWithPrefix('hel');

// Get all entries as [word, value] pairs - O(n)
const entries = trie.entries();

where p is prefix length, n is number of matching words

Examples

Basic Usage with Values

const trie = new Trie<number>();

// Insert words with associated values
trie.insert('hello', 1);
trie.insert('help', 2);
trie.insert('world', 3);

// Search for words
console.log(trie.search('hello')); // 1
console.log(trie.contains('help')); // true
console.log(trie.search('hell')); // null (partial word not stored)

console.log(trie.size); // 3

Case Sensitivity Options

// Case-sensitive trie (default)
const sensitiveTrie = new Trie<number>();
sensitiveTrie.insert('Hello', 1);
console.log(sensitiveTrie.search('Hello')); // 1
console.log(sensitiveTrie.search('hello')); // null

// Case-insensitive trie
const insensitiveTrie = new Trie<number>(false);
insensitiveTrie.insert('Hello', 1);
console.log(insensitiveTrie.search('hello')); // 1
console.log(insensitiveTrie.search('HELLO')); // 1
console.log(insensitiveTrie.search('HeLLo')); // 1

Case Sensitivity

Use case-insensitive mode for user-facing features like search and autocomplete to provide better UX.

Working with Entries

const trie = new Trie<number>();

// Add some entries
trie.insert('one', 1);
trie.insert('two', 2);
trie.insert('three', 3);

// Get all entries as [word, value] pairs
const entries = trie.entries();
for (const [word, value] of entries) {
  console.log(`${word}: ${value}`);
}
// Output:
// one: 1
// two: 2
// three: 3

Phone Directory

interface Contact {
  name: string;
  phone: string;
}

const directory = new Trie<Contact>(false); // Case-insensitive

directory.insert('john', { name: 'John Doe', phone: '555-0100' });
directory.insert('jane', { name: 'Jane Smith', phone: '555-0101' });
directory.insert('joe', { name: 'Joe Brown', phone: '555-0102' });

// Search by prefix
const jContacts = directory.getAllWithPrefix('jo');
console.log(jContacts); // ["john", "joe"]

Error Handling

const trie = new Trie<number>();

// Empty strings are handled gracefully
trie.insert('', 1); // No effect
console.log(trie.search('')); // null

// Non-existent operations return null/false
console.log(trie.search('nonexistent')); // null
console.log(trie.remove('nonexistent')); // false
console.log(trie.contains('nothere')); // false

// Prefix operations with non-existent prefixes
console.log(trie.hasPrefix('xyz')); // false
console.log(trie.getAllWithPrefix('abc')); // []

No Exceptions

Trie methods don't throw exceptions. Search operations return null or false for non-existent keys.

Performance Characteristics

Operation	Time Complexity	Description
insert()	O(m)	Add word with value
search()	O(m)	Find value for word
remove()	O(m)	Remove word
contains()	O(m)	Check if word exists
hasPrefix()	O(p)	Check if prefix exists
getAllWithPrefix()	O(p + n)	Get all words with prefix
entries()	O(n * k)	Get all entries
clear()	O(1)	Remove all words

where:

• m = length of word
• p = length of prefix
• n = number of matching words
• k = average word length

Space Complexity: O(ALPHABET_SIZE × m × n) where n is number of words

Implementation Details

Prefix Sharing

Tries are space-efficient for strings with common prefixes:

Words: "car", "cart", "carpet"

Tree structure:
    c
    |
    a
    |
    r (word: "car")
    |
    t (word: "cart")
    |
    p
    |
    e
    |
    t (word: "carpet")

The prefix "car" is stored only once and shared by all three words.

Memory Management

• Nodes are automatically cleaned up when words are removed
• No circular references
• Efficient memory usage with prefix sharing

When to Use Trie

Perfect for:

• Autocomplete - Get all words with a prefix
• Spell checking - Find similar words
• IP routing - Longest prefix matching
• Dictionary - Fast word lookups
• Search suggestions - Real-time filtering
• Phone directories - Prefix-based contact search

When to Avoid

Consider alternatives when:

• Few common prefixes → Use HashMap/Map for better space efficiency
• Exact matches only → HashMap is simpler and faster O(1) vs O(m)
• Need range queries → Use SortedMap
• Memory constrained → HashMap uses less memory without prefix sharing benefits

Comparison with HashMap

Feature	Trie	HashMap
Exact lookup	O(m)	O(1) average
Prefix search	O(p + n)	O(n × m) (scan all)
Space (similar words)	Efficient	Duplicate storage
Space (unique words)	Higher overhead	More efficient
Autocomplete	Native support	Requires full scan

See Also

Related Examples

• Autocomplete System
• Phone Directory

Other Data Structures

• SortedMap - Key-value store with ordered keys
• RedBlackTree - Sorted unique values