---
categories: String data structures
---
A trie is a data structure that allows quick searches in a dictionary.
Concretely, searching for a word of length $n$ in a trie has a complexity of
$O(n)$, and building a trie has a complexity of $O(L)$, where $L$ is the total
length of the words in the dictionary.
A trie is a tree rooted at an empty node, and in which each way from the root
to a leaf represents a word in the dictionary. In order to accomplish this
task, a node at depth $k$ represents a substring of length $k$, that is the
substring represented by the direct ancestor of the current node plus an
additional character. Of course, the root represents the empty string. If a
certain node represents a whole word in the dictionary, an additional flag
should be used to mark this fact.
## Applications
Tries can be used to compute [longest common prefix](Longest common prefix),
[longest common suffix](Longest common suffix), [longest common
substring](Longest common substring), [string matching](String matching), and
[string matching with mistakes](String matching#variants), to name a few applications.
By [augmenting](Data structure augmentation) tries, it can be made into a very
flexible data structure. See problem [Xor Queries](#problems) for an example.
## Variants
When all [suffixes](String#definitions) of a string are inserted into a trie, the
trie is called a [suffix trie](Suffix trie). This has time and memory
complexity $O(n^2)$, where $n$ is the length of the string. [Suffix
trees](Suffix tree) achieve this in $O(n)$ time and memory by not explicitly
storing all nodes of the trie.
## Implementation in C++
~~~{.cpp}
class Trie{
struct node{
node *next[26]; // Assuming alphabet 'a'-'z'
bool end;
node(){
for(int i=0;i<26;i++)next[i]=this;
end=0;
}
};
node *begin;
public:
Trie(){
begin=new node();
}
void insert(const string &s){
int n=s.length();
node *cur=begin;
for(int i=0;inext[s[i]-'a']!=cur)
cur=cur->next[s[i]-'a'];
else{
node *aux=new node();
cur->next[s[i]-'a']=aux;
cur=aux;
}
}
cur->end=true;
}
bool find(string &s){ // returns true if s is in the input dictionary.
int n=s.length();
node *cur=begin;
for(int i=0;inext[s[i]-'a']!=cur)
cur=cur->next[s[i]-'a'];
else return false;
}
return cur->end;
}
};
~~~
## Problems
- [Bing It On](https://open.kattis.com/problems/bing)
- [Phone List](https://open.kattis.com/problems/phonelist)
- [Xor Queries](https://www.codechef.com/problems/XRQRS) [^1]
## External links
- [Tutorial on Trie and example problems](https://threads-iiith.quora.com/Tutorial-on-Trie-and-example-problems)
[^1]: