# Trie Data Structure: Introduction, implementation and application

*What is it?*

*We are assuming that readers of this article is familiar with tree data structure. A Trie is a special type of tree where each vertex represents a word or prefix while its root contains empty string (“”).*

*root of the tree contains empty string (” “).**Any vertex may represents a word prefix.**The length of child node/vertex is equal to the distance from the root.*

*Let Us look at the below Trie for A trie for keys “A”, “to”, “tea”, “ted”, “ten”, “i”, “in”, and “inn” (source Wikipedia)*

From the above representation it is clear that every vertex represents a word or prefix word but does not represent entire word.

## Operation support

*Trie data structure which build a list of words and provides efficient retrieval/query of information. it should provide at least following operation.*

*search**insert**remove*

*Before implementing Trie let us see How Trie works*

*We know that root of trie contains a null string. Now suppose we need to insert “SAY” in trie. So we have to build a tree of node where each node represents character. The last node is NULL,which shows end of the string.*

*Now add “SAD”*

**Implementation of Trie Data structure and its operation in C++**

## Application of Trie

- Spell Checking
- Data Compression
- IP Address Routing
- Mobile phone contact list

## Leave a Reply