**Trie** is one of my favourite data structures because its easy understand application of Trie and easy to implement as well. In case you don't know Trie comes from the word **Retrieval** because Trie can retrieve several words given prefix of the word. One most common usage of **Trie** that comes in mind quickly is auto completion of word while typing in smartphone soft keyboard. Other possible applications of **Trie** are spell checking keeping full dictionary in a Trie, IP lookup in router etc.

##### Trie Basic Operations:

Operation | Complexity |
---|---|

insertKey() | `O(length of key)` |

searchKey() | `O(length of key)` |

removeKey() | `O(length of key * alphabet size)` |

##### Implementation:

Trie can insert key of any length but with a fixed amount of symbols. Number of symbols are usually denoted by alphabet size. As you can notice above figure a node could have maximum `alphabet size`

number of child nodes. Thus `alphabet size`

should be constant in implementation. Node of a basic **Trie** has 3 properties.

- Reference to parent
- Reference to all children
- Boolean flag that indicates a complete key/word

```
class TrieNode {
TrieNode parent;
TrieNode childs[];
boolean isLeaf;
public TrieNode() {
childs = new TrieNode[MTrie.ALPHABET_SIZE];
}
public TrieNode(boolean isLeaf) {
childs = new TrieNode[MTrie.ALPHABET_SIZE];
this.isLeaf = isLeaf;
}
}
```

**Insert Operation:**

While inserting new key into Trie basically new nodes will be created. Notice root node don't contain any symbol/letter of alphabet. Inserting key/word ** there** will create 5 nodes. Thus length of key is the complexity of this operation.

```
// Complexity: O(length of key)
public boolean insertKey(String key) {
int keyLength = key.length();
TrieNode node = root;
for(int i=0; i < keyLength; i++) {
int value = charValue(key.charAt(i));
if(null == node.childs[value]) node.childs[value] = new TrieNode();
node.childs[value].parent = node;
node = node.childs[value];
}
node.isLeaf = true;
return true;
}
```

**Search Operation:**

Searching a key is as easy as inserting key and that's why same complexity.

```
// Complexity: O(length of key)
public boolean searchKey(String key) {
int keyLength = key.length();
TrieNode node = root;
for(int i=0; i < keyLength; i++) {
int value = charValue(key.charAt(i));
if(null == node.childs[value]) return false;
node = node.childs[value];
}
return node.isLeaf;
}
```

**Remove Operation:**

- First step of removing a key from Trie is to traverse into the key node in which
`isLeaf = true`

. - Second step is checking children existance of the key node. If any child exists you can't remove the node rather mark it as
`isLeaf = false`

. - In case there is no child exists go to up using parent reference until the current node has any child.

In case the figure illustrated above, first traverse to the node ** e** (at bottom), then go up until current node is

**.**

`h`

```
// Complexity: O(length of key * alphabet size)
public boolean removeKey(String key) {
int keyLength = key.length();
TrieNode node = root;
for(int i=0; i < keyLength; i++) {
int value = charValue(key.charAt(i));
if(null == node.childs[value]) return false;
node = node.childs[value];
}
// If the given key isn't a key
if(!node.isLeaf) return false;
// if key node has any other child mark isLeaf == false and return
if(childCount(node) > 0) {
node.isLeaf = false;
return true;
}
// Going bottom to top checking is current node has any child.
// If no child exist current node should be null
for(int i = keyLength-1; i >= 0; i--) {
if(childCount(node) > 0) break;
TrieNode parent = node.parent;
parent.childs[charValue(key.charAt(i))] = null;
node = parent;
}
return true;
}
```

Full Code: Trie_Demo.java