Trie
data-structure-typed / Trie
Class: Trie<R>
Defined in: data-structures/trie/trie.ts:216
Prefix tree (Trie) for fast prefix queries and word storage.
Remarks
Time O(1), Space O(1)
Examples
// Trie isPrefix and isAbsolutePrefix checks
const trie = new Trie(['tree', 'trial', 'trick', 'trip', 'trie']);
// Check if string is a prefix of any word
console.log(trie.hasPrefix('tri')); // true;
console.log(trie.hasPrefix('tr')); // true;
console.log(trie.hasPrefix('xyz')); // false;
// Check if string is an absolute prefix (not a complete word)
console.log(trie.hasPurePrefix('tri')); // true;
console.log(trie.hasPurePrefix('tree')); // false; // 'tree' is a complete word
// Verify size
console.log(trie.size); // 5;
// Trie for autocomplete search index
// Trie is perfect for autocomplete: O(m + k) where m is prefix length, k is results
const searchIndex = new Trie(['typescript', 'javascript', 'python', 'java', 'rust', 'ruby', 'golang', 'kotlin']);
// User types 'j' - get all suggestions
const jResults = searchIndex.getWords('j');
console.log(jResults); // contains 'javascript';
console.log(jResults); // contains 'java';
console.log(jResults.length); // 2;
// User types 'ja' - get more specific suggestions
const jaResults = searchIndex.getWords('ja');
console.log(jaResults); // contains 'javascript';
console.log(jaResults); // contains 'java';
console.log(jaResults.length); // 2;
// User types 'jav' - even more specific
const javResults = searchIndex.getWords('jav');
console.log(javResults); // contains 'javascript';
console.log(javResults); // contains 'java';
console.log(javResults.length); // 2;
// Check for common prefix
console.log(searchIndex.hasCommonPrefix('ja')); // false; // Not all words start with 'ja'
// Total words in index
console.log(searchIndex.size); // 8;
// Get height (depth of tree)
const height = searchIndex.getHeight();
console.log(typeof height); // 'number';
// Dictionary: Case-insensitive word lookup
// Create a case-insensitive dictionary
const dictionary = new Trie<string>([], { caseSensitive: false });
// Add words with mixed casing
dictionary.add('Hello');
dictionary.add('WORLD');
dictionary.add('JavaScript');
// Test lookups with different casings
console.log(dictionary.has('hello')); // true;
console.log(dictionary.has('HELLO')); // true;
console.log(dictionary.has('Hello')); // true;
console.log(dictionary.has('javascript')); // true;
console.log(dictionary.has('JAVASCRIPT')); // true;
// File System Path Operations
const fileSystem = new Trie<string>([
'/home/user/documents/file1.txt',
'/home/user/documents/file2.txt',
'/home/user/pictures/photo.jpg',
'/home/user/pictures/vacation/',
'/home/user/downloads'
]);
// Find common directory prefix
console.log(fileSystem.getLongestCommonPrefix()); // '/home/user/';
// List all files in a directory
const documentsFiles = fileSystem.getWords('/home/user/documents/');
console.log(documentsFiles); // ['/home/user/documents/file1.txt', '/home/user/documents/file2.txt'];
// IP Address Routing Table
// Add IP address prefixes and their corresponding routes
const routes = {
'192.168.1': 'LAN_SUBNET_1',
'192.168.2': 'LAN_SUBNET_2',
'10.0.0': 'PRIVATE_NETWORK_1',
'10.0.1': 'PRIVATE_NETWORK_2'
};
const ipRoutingTable = new Trie<string>(Object.keys(routes));
// Check IP address prefix matching
console.log(ipRoutingTable.hasPrefix('192.168.1')); // true;
console.log(ipRoutingTable.hasPrefix('192.168.2')); // true;
// Validate IP address belongs to subnet
const ip = '192.168.1.100';
const subnet = ip.split('.').slice(0, 3).join('.');
console.log(ipRoutingTable.hasPrefix(subnet)); // true;
Extends
IterableElementBase<string,R>
Type Parameters
R
R = any
- Node Structure: Each node in a Trie represents a string (or a part of a string). The root node typically represents an empty string.
- Child Node Relationship: Each node's children represent the strings that can be formed by adding one character to the string at the current node. For example, if a node represents the string 'ca', one of its children might represent 'cat'.
- Fast Retrieval: Trie allows retrieval in O(m) time complexity, where m is the length of the string to be searched.
- Space Efficiency: Trie can store a large number of strings very space-efficiently, especially when these strings share common prefixes.
- Autocomplete and Prediction: Trie can be used for implementing autocomplete and word prediction features, as it can quickly find all strings with a common prefix.
- Sorting: Trie can be used to sort a set of strings in alphabetical order.
- String Retrieval: For example, searching for a specific string in a large set of strings.
- Autocomplete: Providing recommended words or phrases as a user types.
- Spell Check: Checking the spelling of words.
- IP Routing: Used in certain types of IP routing algorithms.
- Text Word Frequency Count: Counting and storing the frequency of words in a large amount of text data.
Constructors
Constructor
new Trie<R>(words?, options?): Trie<R>;
Defined in: data-structures/trie/trie.ts:225
Create a Trie and optionally bulk-insert words.
Parameters
words?
Iterable<string, any, any> | Iterable<R, any, any>
Iterable of strings (or raw records if toElementFn is provided).
options?
TrieOptions<R>
Options such as toElementFn and caseSensitive.
Returns
Trie<R>
New Trie instance.
Remarks
Time O(totalChars), Space O(totalChars)
Overrides
IterableElementBase.constructor
Properties
caseSensitive
Get Signature
get caseSensitive(): boolean;
Defined in: data-structures/trie/trie.ts:256
Get whether comparisons are case-sensitive.
Remarks
Time O(1), Space O(1)
Returns
boolean
True if case-sensitive.
root
Get Signature
get root(): TrieNode;
Defined in: data-structures/trie/trie.ts:268
Get the root node.
Remarks
Time O(1), Space O(1)
Returns
Root TrieNode.
size
Get Signature
get size(): number;
Defined in: data-structures/trie/trie.ts:244
Get the number of stored words.
Remarks
Time O(1), Space O(1)
Returns
number
Word count.
toElementFn
Get Signature
get toElementFn(): ((rawElement) => E) | undefined;
Defined in: data-structures/base/iterable-element-base.ts:47
Exposes the current toElementFn, if configured.
Remarks
Time O(1), Space O(1).
Returns
((rawElement) => E) | undefined
The converter function or undefined when not set.
Inherited from
IterableElementBase.toElementFn
Methods
[iterator]()
iterator: IterableIterator<string>;
Defined in: data-structures/base/iterable-element-base.ts:60
Returns an iterator over the structure's elements.
Parameters
args
...unknown[]
Optional iterator arguments forwarded to the internal iterator.
Returns
IterableIterator<string>
An IterableIterator<E> that yields the elements in traversal order.
Remarks
Producing the iterator is O(1); consuming the entire iterator is Time O(n) with O(1) extra space.
Inherited from
IterableElementBase.[iterator]
add()
add(word): boolean;
Defined in: data-structures/trie/trie.ts:338
Insert one word into the trie.
Parameters
word
string
Word to insert.
Returns
boolean
True if the word was newly added.
Remarks
Time O(L), Space O(L)
Example
// basic Trie creation and add words
// Create a simple Trie with initial words
const trie = new Trie(['apple', 'app', 'apply']);
// Verify size
console.log(trie.size); // 3;
// Check if words exist
console.log(trie.has('apple')); // true;
console.log(trie.has('app')); // true;
// Add a new word
trie.add('application');
console.log(trie.size); // 4;
addMany()
addMany(words): boolean[];
Defined in: data-structures/trie/trie.ts:403
Insert many words from an iterable.
Parameters
words
Iterable<string, any, any> | Iterable<R, any, any>
Iterable of strings (or raw records if toElementFn is provided).
Returns
boolean[]
Array of per-word 'added' flags.
Remarks
Time O(ΣL), Space O(ΣL)
Example
// Add multiple words
const trie = new Trie();
trie.addMany(['cat', 'car', 'card']);
console.log(trie.has('cat')); // true;
console.log(trie.has('car')); // true;
console.log(trie.size); // 3;
clear()
clear(): void;
Defined in: data-structures/trie/trie.ts:563
Remove all words and reset to a fresh root.
Returns
void
void
Remarks
Time O(1), Space O(1)
Example
// Remove all words
const trie = new Trie(['a', 'b', 'c']);
trie.clear();
console.log(trie.isEmpty()); // true;
Overrides
clone()
clone(): this;
Defined in: data-structures/trie/trie.ts:975
Deep clone this trie by iterating and inserting all words.
Returns
this
A new trie with the same words and options.
Remarks
Time O(ΣL), Space O(ΣL)
Example
// Create independent copy
const trie = new Trie(['hello', 'world']);
const copy = trie.clone();
copy.delete('hello');
console.log(trie.has('hello')); // true;
Overrides
delete()
delete(word): boolean;
Defined in: data-structures/trie/trie.ts:626
Delete one word if present.
Parameters
word
string
Word to delete.
Returns
boolean
True if a word was removed.
Remarks
Time O(L), Space O(1)
Example
// Trie delete and iteration
const trie = new Trie(['car', 'card', 'care', 'careful', 'can', 'cat']);
// Delete a word
trie.delete('card');
console.log(trie.has('card')); // false;
// Word with same prefix still exists
console.log(trie.has('care')); // true;
// Size decreased
console.log(trie.size); // 5;
// Iterate through all words
const allWords = [...trie];
console.log(allWords.length); // 5;
every()
every(predicate, thisArg?): boolean;
Defined in: data-structures/base/iterable-element-base.ts:86
Tests whether all elements satisfy the predicate.
Parameters
predicate
ElementCallback<string, R, boolean>
Function invoked for each element with signature (value, index, self).
thisArg?
unknown
Optional this binding for the predicate.
Returns
boolean
true if every element passes; otherwise false.
Remarks
Time O(n) in the worst case; may exit early when the first failure is found. Space O(1).
Inherited from
filter()
filter(predicate, thisArg?): this;
Defined in: data-structures/trie/trie.ts:1025
Filter words into a new trie of the same class.
Parameters
predicate
ElementCallback<string, R, boolean>
Predicate (word, index, trie) → boolean to keep word.
thisArg?
unknown
Value for this inside the predicate.
Returns
this
A new trie containing words that satisfy the predicate.
Remarks
Time O(ΣL), Space O(ΣL)
Example
// Filter words
const trie = new Trie(['cat', 'car', 'dog', 'card']);
const result = trie.filter(w => w.startsWith('ca'));
console.log(result.size); // 3;
Overrides
find()
Call Signature
find<S>(predicate, thisArg?): S | undefined;
Defined in: data-structures/base/iterable-element-base.ts:162
Finds the first element that satisfies the predicate and returns it.
Finds the first element of type S (a subtype of E) that satisfies the predicate and returns it.
Type Parameters
S
S extends string
Parameters
predicate
ElementCallback<string, R, S>
Type-guard predicate: (value, index, self) => value is S.
thisArg?
unknown
Optional this binding for the predicate.
Returns
S | undefined
The matched element typed as S, or undefined if not found.
Remarks
Time O(n) in the worst case; may exit early on the first match. Space O(1).
Inherited from
Call Signature
find(predicate, thisArg?): string | undefined;
Defined in: data-structures/base/iterable-element-base.ts:163
Finds the first element that satisfies the predicate and returns it.
Finds the first element of type S (a subtype of E) that satisfies the predicate and returns it.
Parameters
predicate
ElementCallback<string, R, unknown>
Type-guard predicate: (value, index, self) => value is S.
thisArg?
unknown
Optional this binding for the predicate.
Returns
string | undefined
The matched element typed as S, or undefined if not found.
Remarks
Time O(n) in the worst case; may exit early on the first match. Space O(1).
Inherited from
forEach()
forEach(callbackfn, thisArg?): void;
Defined in: data-structures/base/iterable-element-base.ts:132
Invokes a callback for each element in iteration order.
Parameters
callbackfn
ElementCallback<string, R, void>
Function invoked per element with signature (value, index, self).
thisArg?
unknown
Optional this binding for the callback.
Returns
void
void.
Remarks
Time O(n), Space O(1).
Inherited from
getHeight()
getHeight(): number;
Defined in: data-structures/trie/trie.ts:668
Compute the height (max depth) of the trie.
Returns
number
Maximum depth from root to a leaf.
Remarks
Time O(N), Space O(H)
getLongestCommonPrefix()
getLongestCommonPrefix(): string;
Defined in: data-structures/trie/trie.ts:831
Return the longest common prefix among all words.
Returns
string
The longest common prefix string.
Remarks
Time O(H), Space O(1)
Example
// Find shared prefix
const trie = new Trie(['flower', 'flow', 'flight']);
console.log(trie.getLongestCommonPrefix()); // 'fl';
getWords()
getWords(
prefix?,
max?,
isAllWhenEmptyPrefix?): string[];
Defined in: data-structures/trie/trie.ts:897
Collect words under a prefix up to a maximum count.
Parameters
prefix?
string = ''
Prefix to match; default empty string for root.
max?
number = Number.MAX_SAFE_INTEGER
Maximum number of words to return; default is Number.MAX_SAFE_INTEGER.
isAllWhenEmptyPrefix?
boolean = false
When true, collect from root even if prefix is empty.
Returns
string[]
Array of collected words (at most max).
Remarks
Time O(K·L), Space O(K·L)
Example
// Trie getWords and prefix search
const trie = new Trie(['apple', 'app', 'apply', 'application', 'apricot']);
// Get all words with prefix 'app'
const appWords = trie.getWords('app');
console.log(appWords); // contains 'app';
console.log(appWords); // contains 'apple';
console.log(appWords); // contains 'apply';
console.log(appWords); // contains 'application';
expect(appWords).not.toContain('apricot');
has()
has(word): boolean;
Defined in: data-structures/trie/trie.ts:463
Check whether a word exists.
Parameters
word
string
Word to search for.
Returns
boolean
True if present.
Remarks
Time O(L), Space O(1)
Example
// Check if a word exists
const dict = new Trie(['apple', 'app', 'application']);
console.log(dict.has('app')); // true;
console.log(dict.has('apple')); // true;
console.log(dict.has('ap')); // false;
Overrides
hasCommonPrefix()
hasCommonPrefix(input): boolean;
Defined in: data-structures/trie/trie.ts:772
Check whether the trie’s longest common prefix equals input.
Parameters
input
string
Candidate longest common prefix.
Returns
boolean
True if input equals the common prefix.
Remarks
Time O(min(H,L)), Space O(1)
hasPrefix()
hasPrefix(input): boolean;
Defined in: data-structures/trie/trie.ts:754
Check whether any word starts with input.
Parameters
input
string
String to test as prefix.
Returns
boolean
True if input matches a path from root.
Remarks
Time O(L), Space O(1)
Example
// Check if a prefix exists
const trie = new Trie(['hello', 'help', 'world']);
console.log(trie.hasPrefix('hel')); // true;
console.log(trie.hasPrefix('wor')); // true;
console.log(trie.hasPrefix('xyz')); // false;
hasPurePrefix()
hasPurePrefix(input): boolean;
Defined in: data-structures/trie/trie.ts:695
Check whether input is a proper prefix of at least one word.
Parameters
input
string
String to test as prefix.
Returns
boolean
True if input is a prefix but not a full word.
Remarks
Time O(L), Space O(1)
isEmpty()
isEmpty(): boolean;
Defined in: data-structures/trie/trie.ts:517
Check whether the trie is empty.
Returns
boolean
True if size is 0.
Remarks
Time O(1), Space O(1)
Example
// Check if empty
const trie = new Trie();
console.log(trie.isEmpty()); // true;
trie.add('word');
console.log(trie.isEmpty()); // false;
Overrides
map()
Call Signature
map<RM>(
callback,
options?,
thisArg?): Trie<RM>;
Defined in: data-structures/trie/trie.ts:1076
Transform words
Type Parameters
RM
RM
Parameters
callback
ElementCallback<string, R, string>
options?
TrieOptions<RM>
thisArg?
unknown
Returns
Trie<RM>
Example
// Transform words
const trie = new Trie(['hello', 'world']);
const upper = trie.map(w => w.toUpperCase());
console.log(upper.has('HELLO')); // true;
Overrides
Call Signature
map<EM, RM>(
callback,
options?,
thisArg?): IterableElementBase<EM, RM>;
Defined in: data-structures/trie/trie.ts:1089
Map words into a new trie (possibly different record type).
Type Parameters
EM
EM
RM
RM
Parameters
callback
ElementCallback<string, R, EM>
Mapping function (word, index, trie) → newWord (string).
options?
TrieOptions<RM>
Options for the output trie (e.g., toElementFn, caseSensitive).
thisArg?
unknown
Value for this inside the callback.
Returns
IterableElementBase<EM, RM>
A new Trie constructed from mapped words.
Remarks
Time O(ΣL), Space O(ΣL)
Overrides
IterableElementBase.map
mapSame()
mapSame(callback, thisArg?): this;
Defined in: data-structures/trie/trie.ts:1116
Map words into a new trie of the same element type.
Parameters
callback
ElementCallback<string, R, string>
Mapping function (word, index, trie) → string.
thisArg?
unknown
Value for this inside the callback.
Returns
this
A new trie with mapped words.
Remarks
Time O(ΣL), Space O(ΣL)
Overrides
print()
print(): void;
Defined in: data-structures/base/iterable-element-base.ts:268
Prints toVisual() to the console. Intended for quick debugging.
Returns
void
void.
Remarks
Time O(n) due to materialization, Space O(n) for the intermediate representation.
Inherited from
reduce()
Reduces all elements to a single accumulated value.
Param
Reducer of signature (acc, value, index, self) => nextAcc. The first element is used as the initial accumulator.
Param
Reducer of signature (acc, value, index, self) => nextAcc.
Param
The initial accumulator value of type E.
Template
The accumulator type when it differs from E.
Param
Reducer of signature (acc: U, value, index, self) => U.
Param
The initial accumulator value of type U.
Remarks
Time O(n), Space O(1). Throws if called on an empty structure without initialValue.
Call Signature
reduce(callbackfn): string;
Defined in: data-structures/base/iterable-element-base.ts:193
Parameters
callbackfn
ReduceElementCallback<string, R>
Returns
string
Inherited from
Call Signature
reduce(callbackfn, initialValue): string;
Defined in: data-structures/base/iterable-element-base.ts:194
Parameters
callbackfn
ReduceElementCallback<string, R>
initialValue
string
Returns
string
Inherited from
Call Signature
reduce<U>(callbackfn, initialValue): U;
Defined in: data-structures/base/iterable-element-base.ts:195
Type Parameters
U
U
Parameters
callbackfn
ReduceElementCallback<string, R, U>
initialValue
U
Returns
U
Inherited from
some()
some(predicate, thisArg?): boolean;
Defined in: data-structures/base/iterable-element-base.ts:109
Tests whether at least one element satisfies the predicate.
Parameters
predicate
ElementCallback<string, R, boolean>
Function invoked for each element with signature (value, index, self).
thisArg?
unknown
Optional this binding for the predicate.
Returns
boolean
true if any element passes; otherwise false.
Remarks
Time O(n) in the worst case; may exit early on first success. Space O(1).
Inherited from
toArray()
toArray(): string[];
Defined in: data-structures/base/iterable-element-base.ts:245
Materializes the elements into a new array.
Returns
string[]
A shallow array copy of the iteration order.
Remarks
Time O(n), Space O(n).
Inherited from
toVisual()
toVisual(): string[];
Defined in: data-structures/base/iterable-element-base.ts:257
Returns a representation of the structure suitable for quick visualization. Defaults to an array of elements; subclasses may override to provide richer visuals.
Returns
string[]
A visual representation (array by default).
Remarks
Time O(n), Space O(n).
Inherited from
values()
values(): IterableIterator<string>;
Defined in: data-structures/base/iterable-element-base.ts:71
Returns an iterator over the values (alias of the default iterator).
Returns
IterableIterator<string>
An IterableIterator<E> over all elements.
Remarks
Creating the iterator is O(1); full iteration is Time O(n), Space O(1).
Inherited from
Protected Members
_toElementFn?
protected optional _toElementFn?: (rawElement) => string;
Defined in: data-structures/base/iterable-element-base.ts:38
The converter used to transform a raw element (R) into a public element (E).
Parameters
rawElement
R
Returns
string
Remarks
Time O(1), Space O(1).
Inherited from
IterableElementBase._toElementFn
Accessors
_total
Get Signature
get protected _total(): number;
Defined in: data-structures/trie/trie.ts:278
(Protected) Get total count for base class iteration.
Remarks
Time O(1), Space O(1)
Returns
number
Total number of elements.
_caseProcess()
protected _caseProcess(str): string;
Defined in: data-structures/trie/trie.ts:1200
(Protected) Normalize a string according to case sensitivity.
Parameters
str
string
Input string to normalize.
Returns
string
Normalized string based on caseSensitive.
Remarks
Time O(L), Space O(L)
_createInstance()
protected _createInstance(options?): this;
Defined in: data-structures/trie/trie.ts:1133
(Protected) Create an empty instance of the same concrete class.
Parameters
options?
TrieOptions<R>
Options forwarded to the constructor.
Returns
this
An empty like-kind trie instance.
Remarks
Time O(1), Space O(1)
_createLike()
protected _createLike<RM>(elements?, options?): Trie<RM>;
Defined in: data-structures/trie/trie.ts:1154
(Protected) Create a like-kind trie and seed it from an iterable.
Type Parameters
RM
RM
Parameters
elements?
Iterable<string, any, any> | Iterable<RM, any, any>
Iterable used to seed the new trie.
options?
TrieOptions<RM>
Options forwarded to the constructor.
Returns
Trie<RM>
A like-kind Trie instance.
Remarks
Time O(ΣL), Space O(ΣL)
_getIterator()
protected _getIterator(): IterableIterator<string>;
Defined in: data-structures/trie/trie.ts:1180
(Protected) Iterate all words in lexicographic order of edges.
Returns
IterableIterator<string>
Iterator of words.
Remarks
Time O(ΣL), Space O(H)
Overrides
IterableElementBase._getIterator
_spawnLike()
protected _spawnLike<RM>(options?): Trie<RM>;
Defined in: data-structures/trie/trie.ts:1170
(Protected) Spawn an empty like-kind trie instance.
Type Parameters
RM
RM
Parameters
options?
TrieOptions<RM>
Options forwarded to the constructor.
Returns
Trie<RM>
An empty like-kind Trie instance.
Remarks
Time O(1), Space O(1)