# Trie Implementation

Posted: 30 Dec, 2020
Difficulty: Moderate

## PROBLEM STATEMENT

#### Implement a Trie Data Structure which supports the following two operations:

``````Operation 1 - insert(word) - To insert a string WORD in the Trie.
Operation 2-  search(word) - To check if a string WORD is present in Trie or not.
``````

#### Trie is a data structure that is like a tree data structure in its organisation. It consists of nodes that store letters or alphabets of words, which can be added, retrieved, and deleted from the trie in a very efficient way. In other words, Trie is an information retrieval data structure, which can beat naive data structures like Hashmap, Tree, etc in the time complexities of its operations.

``````The above figure is the representation of a Trie. New words that are added are inserted as the children of the root node. Alphabets are added in the top to bottom fashion in parent to children hierarchy. Alphabets that are highlighted with blue circles are the end nodes that mark the ending of a word in the Trie.
``````

#### To perform the operations, we denote them in the form of two types of queries:

``````To insert a string WORD in the Trie we use the ‘’Type 1’’ query.
Example - 1 WORD
We will put the integer 1 before the input string WORD to insert it into the trie.

To check if the string WORD is present in Trie or not we use the “Type 2” query.
Example - 2 WORD
We will put integer 2 before the input string WORD to check if it is present in the trie or not.
``````

Example:-

``````Query A - 1 coding
This query will add the string “coding” in the trie.

Query B - 2 coding
This query will see if the string “coding” is present in the trie or not. In this case, as the string “coding” was added in Query A, then this query should return True as the output.
``````
##### Input Format
``````The first line of input contains an integer 'Q' representing the number of queries.
The first and the only line of each query contains an integer ‘T’ denoting the type of query and a string WORD denoting the query string both separated by a single space.
``````
##### Output Format:
``````For each query of Type 2 print "TRUE" if the string WORD is present in Trie or "FALSE" if it is not present.

Note: You don’t have to print anything, it has already been taken care of. Just implement the given functions.
``````
##### Constraints :
``````1 <= Q <= 100000
1 <= | WORD | <= 20

Where 'Q' is the number of queries, and | WORD | is the length of the input string.
Each input string WORD will consist of lower case alphabets (a-z) only.
``````