We can search the trie in O(n) time with n being the length of the word.
Finally, we can implement remove.
To know whether we should remove something, we should first check if the word is in the trie. So first, we'll need to do a search for it and see if we get a depth value returned.
1func (t *Trie) remove(val string) {
2 depth := t.search(val)
3 if depth != 0 {
4 t.removeHelper(t.head, val, depth)
5 }
6}
7
8func (t *Trie) remove(root *TrieNode, key string, depth int) *TrieNode {
9 pCrawl := root
10
11 if pCrawl == nil {
12 return nil
13 }
14
15 if depth == len(key) {
16 if pCrawl.isEndOfWord {
17 pCrawl.isEndOfWord = false
18 }
19 if empty(pCrawl) {
20 pCrawl = nil
21 }
22 return pCrawl
23 }
24 return nil
25}