Begin at the root node.

For each character in the word:

Verify if the current node has a child node for the character.
If not, the word is not present in the Trie.
Move to the child node corresponding to the character.

After processing all characters, check if the end flag of the last node is set to true. If it is, the word is found; if not, the word is not in the Trie.

Check if Trie contains Prefix

Begin at the root node.
For each character in the prefix:
- Check if the current node has a child node for the character.
- If it doesn't, there is no word with the given prefix.
- Move to the child node that corresponds to the character.
If all characters of the prefix are found, return true to indicate that there are words with the given prefix.

Dry Run

For more details, refer to the videos.

Solution

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117