# What's Trie & Implementation?

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="/files/tKFH7xZuj6KLhIndDxM1" 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="/files/b7RWKdo5vhAru3qxHKKq" 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="/files/NGMQtRLAL9gJbSKSCGN8" 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="/files/8FvXULhhbykhlg3aXv91" alt="" width="297"><figcaption></figcaption></figure>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://dsa-cpp.gitbook.io/nafees/trie/whats-trie-and-implementation.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.