## Resources

- Trie Overview
- Trie Overview + Implementation
- Trie Operations + Implementations
- In Depth Trie Explanation
- A good implementation of the delete operation

(Also worth mentioning is this article from the Visual Studio Magazine. The article explains tries and why you might want to use them.)

Takeaways:

- A
**trie**is an ordered tree that compactly stores strings. Each**node**in a trie represents a single character in a string. Say we store the words "car" and "cars" in a trie - the trie would only use four nodes for both - one for each distinct letter of the words (c,a,r,s). - They are also known as
**digital trees**and**prefix trees**. - A trie is most efficient when it is storing strings with similar prefixes, but in general tries are usually not space efficient. They have a space complexity of
`O(n + k)`

. - They are useful for queries involving string prefixes, such as suggesting the next character(s) for a given prefix.
- Tries are not usually found in standard libraries of popular languages (Java & C#, for example, do not have a trie data structure).
- Tries are typically implemented using arrays or hash tables.
- Although hash table implementations are more flexible, array implementations can be more efficient by placing limitations on the trie (like only allowing characters a-z)
- Many trie implementations will use booleans to mark the end of words/strings. But some implementations will use an additional node appended after the last character of the word. This additional node might contain a
`NULL`

value or a special character. - Similarly, the root/head node of a trie can be represented in various ways. For my implementations I used a special character (
`$`

) to denote the root node. - Inserting and searching are both
`O(k)`

operations. - A related data structure is a
**radix tree** - Radix trees are basically a space efficient trie. A trie only stores one character per node, whereas a radix tree can store many. A radix tree is essentially a trie where all nodes that are the only child are merged with their parent nodes - this means less total nodes are required for the same number of words.

Below you will find two trie implementations:

As always, if you found any errors in this post please let me know!

## Discussion (0)