Prefix tree (Trie) for fast prefix queries and word storage.

Time O(1), Space O(1)

// Autocomplete: Prefix validation and checking
const autocomplete = new Trie<string>(['gmail.com', 'gmail.co.nz', 'gmail.co.jp', 'yahoo.com', 'outlook.com']);

// Get all completions for a prefix
const gmailCompletions = autocomplete.getWords('gmail');
console.log(gmailCompletions); // ['gmail.com', 'gmail.co.nz', 'gmail.co.jp']
// 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']
// Autocomplete: Basic word suggestions
// Create a trie for autocomplete
const autocomplete = new Trie<string>([
'function',
'functional',
'functions',
'class',
'classes',
'classical',
'closure',
'const',
'constructor'
]);

// Test autocomplete with different prefixes
console.log(autocomplete.getWords('fun')); // ['functional', 'functions', 'function']
console.log(autocomplete.getWords('cla')); // ['classes', 'classical', 'class']
console.log(autocomplete.getWords('con')); // ['constructor', 'const']

// Test with non-matching prefix
console.log(autocomplete.getWords('xyz')); // []
// 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
// 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

Type Parameters

  • R = any
    1. Node Structure: Each node in a Trie represents a string (or a part of a string). The root node typically represents an empty string.
    2. 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'.
    3. Fast Retrieval: Trie allows retrieval in O(m) time complexity, where m is the length of the string to be searched.
    4. Space Efficiency: Trie can store a large number of strings very space-efficiently, especially when these strings share common prefixes.
    5. 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.
    6. Sorting: Trie can be used to sort a set of strings in alphabetical order.
    7. String Retrieval: For example, searching for a specific string in a large set of strings.
    8. Autocomplete: Providing recommended words or phrases as a user types.
    9. Spell Check: Checking the spelling of words.
    10. IP Routing: Used in certain types of IP routing algorithms.
    11. Text Word Frequency Count: Counting and storing the frequency of words in a large amount of text data.

Hierarchy (view full)

Constructors

  • Create a Trie and optionally bulk-insert words.

    Type Parameters

    • R = any

    Parameters

    • Optionalwords: Iterable<string, any, any> | Iterable<R, any, any> = []

      Iterable of strings (or raw records if toElementFn is provided).

    • Optionaloptions: TrieOptions<R>

      Options such as toElementFn and caseSensitive.

    Returns Trie<R>

    New Trie instance.

    Time O(totalChars), Space O(totalChars)

Properties

_toElementFn?: ((rawElement: R) => string)

The converter used to transform a raw element (R) into a public element (E).

Time O(1), Space O(1).

Accessors

  • get _total(): number
  • (Protected) Get total count for base class iteration.

    Returns number

    Total number of elements.

    Time O(1), Space O(1)

  • get caseSensitive(): boolean
  • Get whether comparisons are case-sensitive.

    Returns boolean

    True if case-sensitive.

    Time O(1), Space O(1)

  • get toElementFn(): undefined | ((rawElement: R) => E)
  • Exposes the current toElementFn, if configured.

    Returns undefined | ((rawElement: R) => E)

    The converter function or undefined when not set.

    Time O(1), Space O(1).

Methods

  • (Protected) Normalize a string according to case sensitivity.

    Parameters

    • str: string

      Input string to normalize.

    Returns string

    Normalized string based on caseSensitive.

    Time O(L), Space O(L)

  • (Protected) Create an empty instance of the same concrete class.

    Parameters

    • Optionaloptions: TrieOptions<R>

      Options forwarded to the constructor.

    Returns this

    An empty like-kind trie instance.

    Time O(1), Space O(1)

  • (Protected) Create a like-kind trie and seed it from an iterable.

    Type Parameters

    • RM

    Parameters

    • Optionalelements: Iterable<string, any, any> | Iterable<RM, any, any> = []

      Iterable used to seed the new trie.

    • Optionaloptions: TrieOptions<RM>

      Options forwarded to the constructor.

    Returns Trie<RM>

    A like-kind Trie instance.

    Time O(ΣL), Space O(ΣL)

  • (Protected) Spawn an empty like-kind trie instance.

    Type Parameters

    • RM

    Parameters

    • Optionaloptions: TrieOptions<RM>

      Options forwarded to the constructor.

    Returns Trie<RM>

    An empty like-kind Trie instance.

    Time O(1), Space O(1)

  • Returns an iterator over the structure's elements.

    Parameters

    • Rest...args: unknown[]

      Optional iterator arguments forwarded to the internal iterator.

    Returns IterableIterator<string, any, any>

    An IterableIterator<E> that yields the elements in traversal order.

    Producing the iterator is O(1); consuming the entire iterator is Time O(n) with O(1) extra space.

  • Insert one word into the trie.

    Parameters

    • word: string

      Word to insert.

    Returns boolean

    True if the word was newly added.

    Time O(L), Space O(L)

  • 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.

    Time O(ΣL), Space O(ΣL)

  • Delete one word if present.

    Parameters

    • word: string

      Word to delete.

    Returns boolean

    True if a word was removed.

    Time O(L), Space O(1)

  • Tests whether all elements satisfy the predicate.

    Parameters

    • predicate: ElementCallback<string, R, boolean>

      Function invoked for each element with signature (value, index, self).

    • OptionalthisArg: unknown

      Optional this binding for the predicate.

    Returns boolean

    true if every element passes; otherwise false.

    Time O(n) in the worst case; may exit early when the first failure is found. Space O(1).

  • Filter words into a new trie of the same class.

    Parameters

    • predicate: ElementCallback<string, R, boolean>

      Predicate (word, index, trie) → boolean to keep word.

    • OptionalthisArg: any

      Value for this inside the predicate.

    Returns this

    A new trie containing words that satisfy the predicate.

    Time O(ΣL), Space O(ΣL)

  • 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 extends string

    Parameters

    • predicate: ElementCallback<string, R, S>

      Type-guard predicate: (value, index, self) => value is S.

    • OptionalthisArg: unknown

      Optional this binding for the predicate.

    Returns undefined | S

    The matched element typed as S, or undefined if not found.

    Time O(n) in the worst case; may exit early on the first match. Space O(1).

  • Invokes a callback for each element in iteration order.

    Parameters

    • callbackfn: ElementCallback<string, R, void>

      Function invoked per element with signature (value, index, self).

    • OptionalthisArg: unknown

      Optional this binding for the callback.

    Returns void

    void.

    Time O(n), Space O(1).

  • Compute the height (max depth) of the trie.

    Returns number

    Maximum depth from root to a leaf.

    Time O(N), Space O(H)

  • Return the longest common prefix among all words.

    Returns string

    The longest common prefix string.

    Time O(H), Space O(1)

  • Collect words under a prefix up to a maximum count.

    Parameters

    • Optionalprefix: string = ''

      Prefix to match; default empty string for root.

    • Optionalmax: number = Number.MAX_SAFE_INTEGER

      Maximum number of words to return; default is Number.MAX_SAFE_INTEGER.

    • OptionalisAllWhenEmptyPrefix: boolean = false

      When true, collect from root even if prefix is empty.

    Returns string[]

    Array of collected words (at most max).

    Time O(K·L), Space O(K·L)

  • 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.

    Time O(min(H,L)), Space O(1)

  • 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.

    Time O(L), Space O(1)

  • 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.

    Time O(L), Space O(1)

  • Maps each element to a new element and returns a new iterable structure.

    Type Parameters

    • RM

      The mapped raw element type used internally by the target structure.

    Parameters

    • callback: ElementCallback<string, R, string>

      Function with signature (value, index, self) => mapped.

    • Optionaloptions: TrieOptions<RM>

      Optional options for the returned structure, including its toElementFn.

    • OptionalthisArg: any

      Optional this binding for the callback.

    Returns Trie<RM>

    A new IterableElementBase<EM, RM> containing mapped elements.

    Time O(n), Space O(n).

  • Map words into a new trie (possibly different record type).

    Type Parameters

    • EM
    • RM

    Parameters

    • callback: ElementCallback<string, R, EM>

      Mapping function (word, index, trie) → newWord (string).

    • Optionaloptions: TrieOptions<RM>

      Options for the output trie (e.g., toElementFn, caseSensitive).

    • OptionalthisArg: any

      Value for this inside the callback.

    Returns IterableElementBase<EM, RM>

    A new Trie constructed from mapped words.

    Time O(ΣL), Space O(ΣL)

  • Map words into a new trie of the same element type.

    Parameters

    • callback: ElementCallback<string, R, string>

      Mapping function (word, index, trie) → string.

    • OptionalthisArg: any

      Value for this inside the callback.

    Returns this

    A new trie with mapped words.

    Time O(ΣL), Space O(ΣL)

  • 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).

    • OptionalthisArg: unknown

      Optional this binding for the predicate.

    Returns boolean

    true if any element passes; otherwise false.

    Time O(n) in the worst case; may exit early on first success. Space O(1).

  • Returns an iterator over the values (alias of the default iterator).

    Returns IterableIterator<string, any, any>

    An IterableIterator<E> over all elements.

    Creating the iterator is O(1); full iteration is Time O(n), Space O(1).