Solution: Implement Trie (Prefix Tree)

Statement

Trie is a tree-like data structure used to store strings. The tries are also called prefix trees because they provide very efficient prefix-matching operations. Implement a trie data structure with three functions that perform the following tasks:

• Insert (word): This inserts a word into the trie.
• Search (word): This searches the given word in the trie and returns TRUE, if found. Otherwise, return FALSE.
• Search prefix (prefix): This searches the given prefix in the trie and returns TRUE, if found. Otherwise, return FALSE.

Constraints:

• $1 \leq$ word.length, prefix.length $\leq 500$