- Trie is a tree data strcuture
- They can store information about keys/numbers/strings in a memory efficient manner
- Their structure consists of nodes, where each node stores a character/bit. We can insert new strings/numbers accordingly.
Here is an example Trie of strings :
-
It’s not the case that a Trie can only be used for strings, it can for example be used for Bits (0 and 1) as well. Some problems in competitive programming are solved by storing the binary representation of numbers in a trie and then processing over them.
-
It can be implemented in 2 ways, using pointers or by using 2D Arrays.
-
For example, you can find my implementation here : Trie using 2D Array
It looks something like this in C++ :
Here are a few coding problems on Trie you can try out :