Package Exports

@datastructures-js/trie

This package does not declare an exports field, so the exports above have been automatically detected and optimized by JSPM instead. If any package subpath is missing, it is recommended to post an issue to the original package (@datastructures-js/trie) to support the "exports" field. If that is not possible, create a JSPM override to customize the exports field for this package.

Readme

@datastructures-js/trie

Trie implementation in javascript. Each Trie node holds one character of a word.

Trie

Install
API
- require
- import
- Construction
- .insert(word)
- .has(word)
- .find(word)
- .remove(word)
- .forEach(cb)
- .toArray()
- .wordsCount()
- .nodesCount()
- .clear()
- TrieNode
Build
License

Install

npm install --save @datastructures-js/trie

API

require

const Trie = require('@datastructures-js/trie');

import

import Trie from '@datastructures-js/trie';

Construction

// example
const englishLang = new Trie();

.insert(word)

insert a string word into the trie.

params
name	type
word	string

return
TrieNode

runtime
O(k) : k = length of the word

Example

englishLang.insert('hi');
englishLang.insert('hit');
englishLang.insert('hide');
englishLang.insert('hello');
englishLang.insert('sand');
englishLang.insert('safe');
englishLang.insert('noun');
englishLang.insert('name');

Note: the empty string is not a default word in the trie. You can add the empty word explicitly using .insert('')

.has(word)

checks if a word exists in the trie.

params
name	type
word	string

return
boolean

runtime
O(k) : k = length of the word

Example

englishLang.has('hi'); // true
englishLang.has('sky'); // false

.find(word)

finds a word in the trie and returns the node of its last character.

params
name	type
word	string

return
TrieNode

runtime
O(k) : k = length of the word

Example

const hi = englishLang.find('hi');
// hi.getChar() = 'i'
// hi.getParent().getChar() = 'h'

const safe = englishLang.find('safe');
// safe.getChar() = 'e'
// safe.getParent().getChar() = 'f'
// safe.getParent().getParent().getChar() = 'a'

.remove(word)

removes a word from the trie.

params
name	type
word	string

return
boolean

runtime
O(k) : k = length of the word

Example

englishLang.remove('hi'); // true - hi removed
englishLang.remove('sky'); // false - nothing is removed

.forEach(cb)

traverses all words in the trie.

params
name	type	description
cb	function	called with each word in the trie

runtime
O(n) : n = number of nodes in the trie

englishLang.forEach((word) => console.log(word));

/*
hit
hide
hello
sand
safe
noun
name
*/

.toArray()

converts the trie into an array of words.

return	description
array	a list of all the words in the trie

runtime
O(n) : n = number of nodes in the trie

Example

console.log(englishLang.toArray());

// ['hit', 'hide', 'hello', 'sand', 'safe', 'noun', 'name']

.wordsCount()

gets the count of words in the trie.

return
number

runtime
O(1)

Example

console.log(englishLang.wordsCount()); // 7

.nodesCount()

gets the count of nodes in the trie.

return
number

runtime
O(1)

Example

console.log(englishLang.nodesCount()); // 23

.clear()

clears the trie.

runtime
O(1)

Example

englishLang.clear();
console.log(englishLang.wordsCount()); // 0
console.log(englishLang.nodesCount()); // 1

TrieNode

.getChar()

returns the node's char.

return
string

.getParent()

returns the parent node.

return
TrieNode

.isEndOfWord()

check if a node is an end of a word.

return
boolean

.getChild(char)

returns the child node of a char.

return
TrieNode

.hasChild(char)

check the node has a child char.

return
boolean

.childrenCount()

returns the number of children nodes.

return
number

Build

grunt build

License

The MIT License. Full License is here