Class Trie<R>

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.

Example

// 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']

Example

// 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']

Example

// 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')); // []

Example

// 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

Example

// 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

Hierarchy (view full)

IterableElementBase<string, R>
- Trie

Index

Constructors

constructor

Accessors

caseSensitive root size

Constructors

constructor

new Trie<R>(words?, options?): Trie<R>
The constructor initializes a Trie data structure with optional options and words provided as input.
Type Parameters
- R = any
Parameters
- words: Iterable<string, any, any> | Iterable<R, any, any> = []
  The words parameter in the constructor is an iterable containing either strings or elements of type R. It is used to initialize the Trie with a list of words or elements. If no words are provided, an empty iterable is used as the default value.
- Optionaloptions: TrieOptions<R>
  The options parameter in the constructor is an optional object that can contain configuration options for the Trie data structure. One of the options it can have is caseSensitive, which is a boolean value indicating whether the Trie should be case-sensitive or not. If caseSensitive is set to `
Returns Trie<R>
Overrides IterableElementBase.constructor
- Defined in trie/trie.ts:186

Accessors

caseSensitive

get caseSensitive(): boolean
The caseSensitive function is a getter that returns the value of the protected _caseSensitive property.

Returns boolean
The value of the _caseSensitive protected variable
- Defined in trie/trie.ts:213

root

get root(): TrieNode
The root function returns the root node of the tree.

Returns TrieNode
The root node
- Defined in trie/trie.ts:223

size

get size(): number
The size function returns the size of the stack.

Returns number
The number of elements in the list
- Defined in trie/trie.ts:203

Methods

`Protected`_caseProcess

_caseProcess(str): string
Protected
Time Complexity: O(l), where l is the length of the input string. Space Complexity: O(1) - Constant space.
Parameters
- str: string
Returns string
- Defined in trie/trie.ts:623

`Protected`_getIterator

_getIterator(): IterableIterator<string, any, any>
Time Complexity: O(n) Space Complexity: O(n)

The function _getIterator returns an iterable iterator that performs a depth-first search on a trie data structure and yields all the paths to the end nodes.

Returns IterableIterator<string, any, any>
Overrides IterableElementBase._getIterator
- Defined in trie/trie.ts:599

[iterator]

[iterator](...args): IterableIterator<string, any, any>
Time Complexity: O(n) Space Complexity: O(1)

The function is an implementation of the Symbol.iterator method that returns an IterableIterator.
Parameters
- Rest...args: any[]
  The args parameter in the code snippet represents a rest parameter. It allows the function to accept any number of arguments as an array. In this case, the args parameter is used to pass any number of arguments to the _getIterator method.
Returns IterableIterator<string, any, any>
Inherited from IterableElementBase.[iterator]
- Defined in base/iterable-element-base.ts:32

add

add(word): boolean
Time Complexity: O(l), where l is the length of the word being added. Space Complexity: O(l) - Each character in the word adds a TrieNode.

Add a word to the Trie structure.
Parameters
- word: string
  The word to add.
Returns boolean
True if the word was successfully added.
- Defined in trie/trie.ts:235

addMany

addMany(words): boolean[]
Time Complexity: O(n * l) Space Complexity: O(1)

The addMany function in TypeScript takes an iterable of strings or elements of type R, converts them using a provided function if available, and adds them to a data structure while returning an array of boolean values indicating success.
Parameters
- words: Iterable<string, any, any> | Iterable<R, any, any>
  The words parameter in the addMany function is an iterable that contains either strings or elements of type R.
Returns boolean[]
The addMany method returns an array of boolean values indicating whether each word in the input iterable was successfully added to the data structure.
- Defined in trie/trie.ts:267

clear

clear(): void
Time Complexity: O(1) Space Complexity: O(1)

The clear function resets the size of the Trie to 0 and creates a new root TrieNode.

Returns void
Overrides IterableElementBase.clear
- Defined in trie/trie.ts:315

clone

clone(): Trie<R>
Time Complexity: O(n) Space Complexity: O(n)

The clone function returns a new instance of the Trie class with the same values and case sensitivity as the original Trie.

Returns Trie<R>
A new instance of the Trie class is being returned.
Overrides IterableElementBase.clone
- Defined in trie/trie.ts:530

delete

delete(word): boolean
Time Complexity: O(l), where l is the length of the word being deleted. Space Complexity: O(n) - Due to the recursive DFS approach.

Remove a word from the Trie structure. @param{string} word - The word to delete.
Parameters
- word: string
Returns boolean
True if the word was successfully removed.
- Defined in trie/trie.ts:328

every

every(predicate, thisArg?): boolean
Time Complexity: O(n) Space Complexity: O(1)

The every function checks if every element in the array satisfies a given predicate.
Parameters
- predicate: ElementCallback<string, R, boolean>
  The predicate parameter is a callback function that takes three arguments: the current element being processed, its index, and the array it belongs to. It should return a boolean value indicating whether the element satisfies a certain condition or not.
- OptionalthisArg: any
  The thisArg parameter is an optional argument that specifies the value to be used as this when executing the predicate function. If thisArg is provided, it will be passed as the this value to the predicate function. If thisArg is
Returns boolean
The every method is returning a boolean value. It returns true if every element in the array satisfies the provided predicate function, and false otherwise.
Inherited from IterableElementBase.every
- Defined in base/iterable-element-base.ts:62

filter

filter(predicate, thisArg?): Trie<R>
Time Complexity: O(n) Space Complexity: O(n)

The filter function takes a predicate function and returns a new array containing all the elements for which the predicate function returns true.
Parameters
- predicate: ElementCallback<string, R, boolean>
  The predicate parameter is a callback function that takes three arguments: word, index, and this. It should return a boolean value indicating whether the current element should be included in the filtered results or not.
- OptionalthisArg: any
  The thisArg parameter is an optional argument that allows you to specify the value of this within the predicate function. It is used when you want to bind a specific object as the context for the predicate function. If thisArg is provided, it will be
Returns Trie<R>
The filter method is returning an array of strings (string[]).
Overrides IterableElementBase.filter
- Defined in trie/trie.ts:548

find

find<S>(predicate, thisArg?): undefined | S
Type Parameters
- S extends string
Parameters
- predicate: ElementCallback<string, R, S>
- OptionalthisArg: any
Returns undefined | S
Inherited from IterableElementBase.find
- Defined in base/iterable-element-base.ts:116
find(predicate, thisArg?): undefined | string
Parameters
- predicate: ElementCallback<string, R, unknown>
- OptionalthisArg: any
Returns undefined | string
Inherited from IterableElementBase.find
- Defined in base/iterable-element-base.ts:117

forEach

forEach(callbackfn, thisArg?): void
Time Complexity: O(n) Space Complexity: O(1)

The forEach function iterates over each element in an array-like object and calls a callback function for each element.
Parameters
- callbackfn: ElementCallback<string, R, void>
  The callbackfn parameter is a function that will be called for each element in the array. It takes three arguments: the current element being processed, the index of the current element, and the array that forEach was called upon.
- OptionalthisArg: any
  The thisArg parameter is an optional argument that specifies the value to be used as this when executing the callbackfn function. If thisArg is provided, it will be passed as the this value to the callbackfn function. If `thisArg
Returns void
Inherited from IterableElementBase.forEach
- Defined in base/iterable-element-base.ts:109

getHeight

getHeight(): number
Time Complexity: O(n) Space Complexity: O(1)

The function getHeight calculates the height of a trie data structure starting from the root node.

Returns number
The getHeight method returns the maximum depth or height of the trie tree starting from the root node. It calculates the depth using a breadth-first search (BFS) traversal of the trie tree and returns the maximum depth found.
- Defined in trie/trie.ts:374

getLongestCommonPrefix

getLongestCommonPrefix(): string
Time Complexity: O(n), where n is the total number of nodes in the trie. Space Complexity: O(l), where l is the length of the longest common prefix.

Get the longest common prefix among all the words stored in the Trie.

Returns string
The longest common prefix found in the Trie.
- Defined in trie/trie.ts:461

getWords

getWords(prefix?, max?, isAllWhenEmptyPrefix?): string[]
Time Complexity: O(w * l), where w is the number of words retrieved, and l is the average length of the words. Space Complexity: O(w * l) - The space required for the output array.

The getAll function returns an array of all words in a Trie data structure that start with a given prefix.
Parameters
- prefix: string = ''
  The prefix parameter is a string that represents the prefix that we want to search for in the trie. It is an optional parameter, so if no prefix is provided, it will default to an empty string.
- max: number = Number.MAX_SAFE_INTEGER
  The max count of words will be found
- isAllWhenEmptyPrefix: boolean = false
  If true, when the prefix provided as '', returns all the words in the trie.
Returns string[]
an array of strings.
- Defined in trie/trie.ts:484

has

has(word): boolean
Time Complexity: O(l), where l is the length of the input word. Space Complexity: O(1) - Constant space.

Check if the Trie contains a given word.
Parameters
- word: string
  The word to check for.
Returns boolean
True if the word is present in the Trie.
Overrides IterableElementBase.has
- Defined in trie/trie.ts:287

hasCommonPrefix

hasCommonPrefix(input): boolean
Time Complexity: O(n), where n is the total number of nodes in the trie. Space Complexity: O(l), where l is the length of the input prefix.

Check if the input string is a common prefix in the Trie, meaning it's a prefix shared by all words in the Trie.
Parameters
- input: string
  The input string representing the common prefix to check for.
Returns boolean
True if it's a common prefix in the Trie.
- Defined in trie/trie.ts:440

hasPrefix

hasPrefix(input): boolean
Time Complexity: O(l), where l is the length of the input prefix. Space Complexity: O(1) - Constant space.

Check if a given input string is a prefix of any existing word in the Trie, whether as an absolute prefix or a complete word.
Parameters
- input: string
  The input string representing the prefix to check.
Returns boolean
True if it's a prefix in the Trie.
- Defined in trie/trie.ts:421

hasPurePrefix

hasPurePrefix(input): boolean
Time Complexity: O(l), where l is the length of the input prefix. Space Complexity: O(1) - Constant space.

Check if a given input string has an absolute prefix in the Trie, meaning it's not a complete word.
Parameters
- input: string
  The input string to check.
Returns boolean
True if it's an absolute prefix in the Trie.
- Defined in trie/trie.ts:402

isEmpty

isEmpty(): boolean
Time Complexity: O(1) Space Complexity: O(1)

The isEmpty function checks if the size of the queue is 0.

Returns boolean
True if the size of the queue is 0
Overrides IterableElementBase.isEmpty
- Defined in trie/trie.ts:305

map

map<RM>(callback, toElementFn?, thisArg?): Trie<RM>
Time Complexity: O(n) Space Complexity: O(n)

The map function creates a new Trie by applying a callback function to each element in the current Trie.
Type Parameters
- RM
Parameters
- callback: ElementCallback<string, R, string>
  The callback parameter is a function that will be called for each element in the Trie. It takes four arguments:
- OptionaltoElementFn: ((rawElement: RM) => string)
  The toElementFn parameter is an optional function that can be used to convert the raw element (RM) into a string representation. This can be useful if the raw element is not already a string or if you want to customize how the element is converted into a string. If this parameter is
  - - (rawElement): string
    - Parameters
      rawElement: RM
      Returns string
- OptionalthisArg: any
  The thisArg parameter is an optional argument that allows you to specify the value of this within the callback function. It is used to set the context or scope in which the callback function will be executed. If thisArg is provided, it will be used as the value of
Returns Trie<RM>
a new Trie object.
Overrides IterableElementBase.map
- Defined in trie/trie.ts:578

print

print(): void
Time Complexity: O(n) Space Complexity: O(n)

The print function logs the elements of an array to the console.

Returns void
Inherited from IterableElementBase.print
- Defined in base/iterable-element-base.ts:214

reduce

reduce(callbackfn): string
Parameters
- callbackfn: ReduceElementCallback<string, R>
Returns string
Inherited from IterableElementBase.reduce
- Defined in base/iterable-element-base.ts:161
reduce(callbackfn, initialValue): string
Parameters
- callbackfn: ReduceElementCallback<string, R>
- initialValue: string
Returns string
Inherited from IterableElementBase.reduce
- Defined in base/iterable-element-base.ts:162
reduce<U>(callbackfn, initialValue): U
Type Parameters
- U
Parameters
- callbackfn: ReduceElementCallback<string, R, U>
- initialValue: U
Returns U
Inherited from IterableElementBase.reduce
- Defined in base/iterable-element-base.ts:163

some

some(predicate, thisArg?): boolean
Time Complexity: O(n) Space Complexity: O(1)

The "some" function checks if at least one element in a collection satisfies a given predicate.
Parameters
- predicate: ElementCallback<string, R, boolean>
  The predicate parameter is a callback function that takes three arguments: value, index, and array. It should return a boolean value indicating whether the current element satisfies the condition.
- OptionalthisArg: any
  The thisArg parameter is an optional argument that specifies the value to be used as the this value when executing the predicate function. If thisArg is provided, it will be passed as the this value to the predicate function. If `thisArg
Returns boolean
a boolean value. It returns true if the predicate function returns true for any element in the collection, and false otherwise.
Inherited from IterableElementBase.some
- Defined in base/iterable-element-base.ts:86

toArray

toArray(): string[]
Time Complexity: O(n) Space Complexity: O(n)

The toArray function converts a linked list into an array.

Returns string[]
The toArray() method is returning an array of type E[].
Inherited from IterableElementBase.toArray
- Defined in base/iterable-element-base.ts:194

toVisual

toVisual(): string[]
Time Complexity: O(n) Space Complexity: O(n)

The print function logs the elements of an array to the console.

Returns string[]
Inherited from IterableElementBase.toVisual
- Defined in base/iterable-element-base.ts:204

values

values(): IterableIterator<string, any, any>
Time Complexity: O(n) Space Complexity: O(n)

The function returns an iterator that yields all the values in the object.

Returns IterableIterator<string, any, any>
Inherited from IterableElementBase.values
- Defined in base/iterable-element-base.ts:42

Class Trie<R>

Example

Example

Example

Example

Example

Type Parameters

Hierarchy (view full)

Index

Constructors

Accessors

Methods

Constructors

constructor

Type Parameters

Parameters

Returns Trie<R>

Accessors

caseSensitive

Returns boolean

root

Returns TrieNode

size

Returns number

Methods

Protected_caseProcess

Parameters

Returns string

Protected_getIterator

Returns IterableIterator<string, any, any>

[iterator]

Parameters

Returns IterableIterator<string, any, any>

add

Parameters

Returns boolean

addMany

Parameters

Returns boolean[]

clear

Returns void

clone

Returns Trie<R>

delete

Parameters

Returns boolean

every

Parameters

Returns boolean

filter

Parameters

Returns Trie<R>

find

Type Parameters

Parameters

Returns undefined | S

Parameters

Returns undefined | string

forEach

Parameters

Returns void

getHeight

Returns number

getLongestCommonPrefix

Returns string

getWords

Parameters

Returns string[]

has

Parameters

Returns boolean

hasCommonPrefix

Parameters

Returns boolean

hasPrefix

Parameters

Returns boolean

hasPurePrefix

Parameters

Returns boolean

`Protected`_caseProcess

`Protected`_getIterator