Trie Tree Implementation using JS

I. What is Trie

Trie is an efficient information reTrieval data structure.

  1. search complexities can be brought to optimal limit (key length).
  2. If we store keys in BST, a well balanced BST will need time proportional to O(M*log N), where M is maximum string length, and N is number of keys in tree
  3. Using Trie, we can search the key in O(M) time.

II. Use case

  1. Prefix matching
  2. Check if a word exists in a dictionary
  3. Word frequency in dictionary
  4. Sort Words in dictionary

III. Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
/* 			
*
/ | \
a c o
/ | | |
c t a f
/ | \
e t b

For a word of length K, we need (K+1) nodes to store
- `add`: [1] *.children.a
[2] a.children.c
[3] c.children.d
[4] e.children.isEnd = true
*/

class TrieNode{
constructor(){
this.isEnd = false
this.freq = 0
this.children = {}
}
}

class Trie{
constructor(){
this.root = new TrieNode()
}

insert(word){
if( word.length === 0 ) return // forbid empty string
let letter, curNode = this.root
for( let i = 0; i < word.length; i++ ){
letter = word[i]
if( !curNode.children.hasOwnProperty(letter) ){
curNode.children[letter] = new TrieNode()
}
curNode = curNode.children[letter]
}
curNode.isEnd = true
curNode.freq = curNode.freq + 1
}

getNodeForPrefix(str){
let letter, curNode = this.root
for( let i = 0; i < str.length; i++ ){
letter = str[i]
if( !curNode.children.hasOwnProperty(letter) )
return null
curNode = curNode.children[letter]
}
return curNode
}

isWord(word){
if( this.getNodeForPrefix(word) === null ) return false
return this.getNodeForPrefix(word).isEnd
}

getWordFreq(word){
if( this.getNodeForPrefix(word) === null ) return false
return this.getNodeForPrefix(word).freq
}
}


/* -------------------- Testing --------------------*/

let ace = "ace"
let at = "at"
let cat = "cat"
let cab = "cab"
let of = "of"

let t = new Trie()
t.insert(ace)
console.log(t.isWord(ace)) // true

t.insert(ace)
console.log(t.isWord(ace)) // true
console.log(t.getWordFreq(ace))// 2

t.insert(at)
console.log(t.isWord(at)) // true
console.log(t.getWordFreq(at)) // 1

t.insert(cat)
t.insert(cat)
console.log(t.isWord(cat)) // true
console.log(t.getWordFreq(cat))// 2
t.insert(cat)
console.log(t.getWordFreq(cat))// 3

t.insert(cab)
console.log(t.isWord(cab)) // true
console.log(t.getWordFreq(cab))// 1

t.insert(of)
console.log(t.isWord(of)) // true
console.log(t.getWordFreq(of))// 1

// check the internal representation of the Trie
console.log(t.root)