Trie Data Structure Implementation

Design and implement a Trie (Prefix Tree) which should support the following two operations:

1. Insert a word into the Trie. The operation is marked as 'insert(word)'. 2. Search for a word in the Trie. The operation is marked as 'search(word)'.

The Trie is a tree-like data structure that efficiently stores a dynamic set of strings, where the keys are usually strings. Interactive operations like insert and search in a Trie significantly outperform those in naive data structures such as hashmaps and binary search trees in terms of time complexity.

Input/Output

Input:

The first input line contains an integer 'Q' indicating the number of queries. Each query line contains an integer 'T' (indicating the type of query) followed by a space and a string 'WORD'.

Output:

For each Type 2 query, print 'TRUE' if 'WORD' is found in the Trie and 'FALSE' otherwise.

Example:

Input: 3 1 coding 1 code 2 coding Output: TRUE

Constraints:

1

Question

Trie Data Structure Implementation

Design and implement a Trie (Prefix Tree) which should support the following two operations:

1. Insert a word into the Trie. The operation is marked as 'insert(word)'.
2. Search for a word in the Trie. The operation is marked as 'search(word)'.

The Trie is a tree-like data structure that efficiently stores a dynamic set of strings, where the keys are usually strings. Interactive operations like insert and search in a Trie significantly outperform those in naive data structures such as hashmaps and binary search trees in terms of time complexity.

Input/Output

Input:

The first input line contains an integer 'Q' indicating the number of queries.
Each query line contains an integer 'T' (indicating the type of query) followed by a space and a string 'WORD'.

Output:

For each Type 2 query, print 'TRUE' if 'WORD' is found in the Trie and 'FALSE' otherwise.

Example:

Input:
3
1 coding
1 code
2 coding

Output:
TRUE

Constraints:

1 <= Q <= 100000
1 <= |WORD| <= 20
Each 'WORD' consists of lowercase alphabets (a-z) only.

Note:

Implement the requested functions and handle the input/output as per instruction. Do not format input/output within the function itself.

Accepted Answer

Implement a Trie data structure supporting insert and search operations efficiently.

Implement a Trie class with insert and search methods.
Use a nested class Node to represent each node in the Trie.
For insert operation, iterate through each character in the word and create nodes as needed.
For search operation, traverse the Trie based on the characters in the word to check for existence.
Return 'TRUE' if the word is found in the Trie, 'FALSE' otherwise.