In this blog post we are going to learn 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.

Trie Data Structure Introduction implementation and applicationNow add “NO”


Now add “SAD”


Implementation of Trie Data structure and its operation in C

Click here to learn how to implement trie in c

Application of Trie

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

Related Contents to follow