# Check the consistency of the numbers (Trie Data Structure Question)

EARTH is receiving some weird signals for the past few days. After converting them to our number system they found out that some numbers are repeating. Due to traveling, millions of miles signal gets distorted. Now they asked you to check the consistency of their data sets. The consistency is that no number is the prefix another number in that data set.

**Input:**

Input starts with an integer **T (≤ 50)**, denoting the number of test cases. Each case starts with an integer **n (1 ≤ n ≤ 100000)** denoting the total numbers in their list. Each of the next n lines contains one unique phone number. A number is a sequence of digits and has a length from **1** to **10**.

**Output:**

For each case, print the case number and **'YES'** if the list is consistent or **'NO'** if it's not.

**Example with explanation:**

Input:
T = 1 // Test case
N = 3
911
9629986
9112545643
Output:
"NO"
Since the number 911 has occurred in the third case 9112545643.
Hence it is not consistent.
Input:
T = 1 // Test case
N = 4
1234
1243
1342
3212
Output:
"YES"
Since there is no number which is prefix of any other number.

Since there are various methods to solve this type of problem but the major issue here is the time constraint. So to pass all the test cases we need to think of a data structure which can help to pass all the test cases, here we would use

"TRIE"data structure, in which to search a string of lengthand if there areMsuch Nodes it takesNO(M)to search the Key present in a node.Every node of Trie consists of multiple branches. Each branch represents a possible character of keys. We need to mark the last node of every key as the end of the word node. A Trie node field stop is used to distinguish the node as the end of the word node. A simple structure to represent nodes of the English alphabet can be as following,

Inserting a key to Trie is a simple approach. Every character of the input key is inserted as an individual Trie node. Note that the next is an array of pointers (or references) to next level trie nodes. The key character acts as an index into the array of children. If the input key is new or an extension of the existing key, we need to construct non-existing nodes of the key and mark the end of the word for the last node. If the input key is a prefix of the existing key in Trie, we simply mark the last node of the key as the stop=1.

Searching for a key is similar to insert operation, however, we only compare the characters and move down. The search can terminate due to the end of a string or lack of key in the trie.

C++ Implementation:

need an explanation for this answer? contact us directly to get an explanation for this answerOutput