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.
1public void Remove(string val) {
2 int depth = this.Search(val);
3 if (depth != 0) {
4 RemoveHelper(this.head, val, depth);
5 }
6}
7
8public TrieNode Remove(TrieNode root, string key, int depth = 0) {
9 TrieNode pCrawl = root;
10
11 if (pCrawl == null)
12 return null;
13
14 if (depth == key.Length) {
15 if (pCrawl.IsEndOfWord)
16 pCrawl.IsEndOfWord = false;
17
18 if (IsEmpty(pCrawl))
19 pCrawl = null;
20
21 return pCrawl;
22 }
23}