Leetcode List: https://leetcode.com/list/5uyupjcr

So let's start with,

What is Trie?

• Trie is a tree-like data structure wherein all the nodes stores alphabetical values (most commonly).
• Trie is an ordered tree data structure in which every traversal down the branch retrieves you a string or word.

Here is a formal definition from Wikipedia, A trie also called a digital tree or prefix tree, is a kind of search tree—an ordered tree data structure used to store a dynamic set or associative array where the keys are usually strings.Fun Fact: Trie name comes from name retrieval.

• Representation:

It contains an empty root node and references to all other nodes.

The number of references depends on the total number of values possible.Example: If the trie represents strings that contain only lowercase letters. Then the number of references needs to be 26 since there are 26 different alphabets from 'a' to 'z'. If trie represents bits it has only two references. (0 and 1)

To be more clear, What does a node contains? It contains two parts.

• The array of references to other nodes.
• Boolean value - leaf (To check whether the string ends at that node or not) Note here leaf is not to check whether it is leaf node or not.
• Let's take an example and build a trie.

I hope it made some sense.

Template for build trie and search a string in a trie:

	TrieNode* root = new TrieNode();        /* Root Creation */

    void insert(string word) {              /* Insert word into the trie */
        TrieNode* node = root;
        for(char c : word){
            if(!node -> children[c - 'a']){
                node -> children[c - 'a'] = new TrieNode();
            }
            node = node -> children[c - 'a'];
        }
        node -> end = true;
    }

    bool search(string word) {             /* Search word into the trie */
        TrieNode* node = root;
        for(char c : word){
            if(!node -> children[c - 'a']){
                return false;
            }
            node = node -> children[c - 'a'];
        }
        return node -> end;
    }

If you still have a hard time understanding it. I attached some articles and youtube videos to help you.

• [Medium Article basecs](https://medium.com/basecs/trying-to-understand-tries-3ec6bede0014#:~:text=A trie is a tree,are a relatively new thing.)
• Trie - Wikipedia