Trie implementation in javascript. Each Trie node holds one character of a word.
npm install --save @datastructures-js/trie
const { Trie, TrieNode } = require('@datastructures-js/trie');
import { Trie, TrieNode } from '@datastructures-js/trie';
const dictionary = new Trie();
insert the string form of value (value.toString()
) into the trie.
Note: the empty string is not a default word in the trie. empty word can be added by explicitly calling .insert('')
dictionary
.insert('hi')
.insert('hit')
.insert('hide')
.insert('hello')
.insert('sand')
.insert('safe')
.insert('noun')
.insert('name');
checks if a word exists in the trie.
dictionary.has('hi'); // true
dictionary.has('sky'); // false
finds a word in the trie and returns the node of its last character.
const hi = dictionary.find('hi');
// hi.getChar() = 'i'
// hi.getParent().getChar() = 'h'
const safe = dictionary.find('safe');
// safe.getChar() = 'e'
// safe.getParent().getChar() = 'f'
// safe.getParent().getParent().getChar() = 'a'
const nothing = dictionary.find('nothing'); // null
removes a word from the trie.
dictionary.remove('hi'); // hi
// none existing word
dictionary.remove('sky'); // null
traverses all words in the trie.
dictionary.forEach((word) => console.log(word));
/*
hit
hide
hello
sand
safe
noun
name
*/
converts the trie into an array of words.
console.log(dictionary.toArray());
// ['hit', 'hide', 'hello', 'sand', 'safe', 'noun', 'name']
gets the count of words in the trie.
console.log(dictionary.wordsCount()); // 7
gets the count of nodes in the trie.
console.log(dictionary.nodesCount()); // 23
clears the trie.
dictionary.clear();
console.log(dictionary.wordsCount()); // 0
console.log(dictionary.nodesCount()); // 1
converts an existing array of values into a trie.
const numbersTrie = Trie.fromArray([1, 32, 123, 21, 222, 132, 111, 312]);
console.log(numbersTrie.wordsCount()); // 8
console.log(numbersTrie.has('132')); // true
console.log(numbersTrie.has(123)); // true
checks if node is root.
checks if has no children.
gets the node's char.
gets the node's parent node.
sets the node's parent node.
checks if node's char is last in a word.
sets if node's char is last in a word.
gets the node's child from a char.
checks if the node has a child from a char.
gets the node's children count.
grunt build
The MIT License. Full License is here