> For the complete documentation index, see [llms.txt](https://dsa-cpp.gitbook.io/nafees/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://dsa-cpp.gitbook.io/nafees/trie/whats-trie-and-implementation.md).

# What's Trie & Implementation?

Trie Data Structure

Trie basically comes from the word R&#x65;*<mark style="color:red;">**trie**</mark>*&#x76;al.

* 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

<figure><img src="https://3848643327-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F07O01HTuDHqLK3IxhYPe%2Fuploads%2FGEb3Ztgf5HtSm5hLD5Qv%2FScreenshot_2024-02-27_150537-removebg-preview.png?alt=media&amp;token=c2284a00-f3b2-47c0-824c-2e278050ba1a" alt="" width="217"><figcaption></figcaption></figure>

## Applications&#x20;

### <mark style="color:blue;">Auto-Complete words</mark>

* 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.

<figure><img src="https://3848643327-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F07O01HTuDHqLK3IxhYPe%2Fuploads%2F0iH7r5P79tdBD9tTEsNK%2Fimage.png?alt=media&amp;token=b6222eab-8738-4983-8e7b-929c1a1cac56" alt=""><figcaption></figcaption></figure>

### <mark style="color:blue;">Search Contacts in the phone</mark>

* 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.

### <mark style="color:blue;">Spell Checking</mark>

* 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.

<figure><img src="https://3848643327-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F07O01HTuDHqLK3IxhYPe%2Fuploads%2FS1cPQ8XoSkTR0uphOwxp%2Fimage.png?alt=media&amp;token=77edf260-bf3a-45dc-8e7c-5306cf7080dc" alt=""><figcaption></figcaption></figure>

## What is a TrieNode?

* A <mark style="color:red;">TrieNode</mark> in a Trie represents a <mark style="color:purple;">single</mark> alphabet of the word.
* In the below example, to insert the word "dog" 3 TrieNodes are used, one for each alphabet.

<figure><img src="https://3848643327-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F07O01HTuDHqLK3IxhYPe%2Fuploads%2Ff9TOjTUwpfzHePL6FGCL%2FScreenshot_2024-02-27_152540-removebg-preview.png?alt=media&amp;token=ab3673ba-eb7f-4f97-a2c5-4dd532b9715e" alt="" width="297"><figcaption></figcaption></figure>