# LeetCode 208. Implement Trie (Prefix Tree)

Implement Trie (Prefix Tree)

```public class Trie {
class TrieNode {
public TrieNode[] Children = new TrieNode[26];
public bool IsWord = false;
}

TrieNode Root = new TrieNode();

/** Initialize your data structure here. */
public Trie() {

}

/** Inserts a word into the trie. */
public void Insert(string word) {
TrieNode cur = Root;
for(int i = 0; i < word.Length; i++){
int index = word[i] - 'a';
if(cur.Children[index] == null) cur.Children[index] = new TrieNode();
cur = cur.Children[index];
}
cur.IsWord = true;
}

/** Returns if the word is in the trie. */
public bool Search(string word) {
TrieNode cur = Root;
for(int i = 0; i < word.Length; i++){
int index = word[i] - 'a';
if(cur.Children[index] == null) return false;
cur = cur.Children[index];
}
if(cur.IsWord) return true;
return false;
}

/** Returns if there is any word in the trie that starts with the given prefix. */
public bool StartsWith(string prefix) {
TrieNode cur = Root;
for(int i = 0; i < prefix.Length; i++){
int index = prefix[i] - 'a';
if(cur.Children[index] == null) return false;
cur = cur.Children[index];
}
return true;
}

}

/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.Insert(word);
* bool param_2 = obj.Search(word);
* bool param_3 = obj.StartsWith(prefix);
*/
```