What's Trie & Implementation?

Trie Data Structure

Trie basically comes from the word Retrieval.

• The main purpose of this data structure is to retrieve stored information very fast.

• A Trie with 4 words

  1. dog

  2. dust

  3. hat

  4. home

Applications

Auto-Complete words

• Auto-complete feature is implemented by Tries.

• Many websites have used auto-complete features, which suggest the user rest of the word, while the user is typing.

Search Contacts in the phone

• Searching for a person's contact number in a contact list is efficiently implemented by Trie. As soon as the user enters letters the application auto-suggests the name of the person.

Spell Checking

• Tries help to check and correct word spelling entered by the user. In case the user doesn't know the exact spelling it auto-suggests the correct spelling.

What is a TrieNode?

• A TrieNode in a Trie represents a single alphabet of the word.

• In the below example, to insert the word "dog" 3 TrieNodes are used, one for each alphabet.