Search in a Trie
Explore how to search for words in a trie by tracing character paths and considering cases such as missing words or substrings that are not full words. Understand the importance of the endOfWord flag in successful searches and learn the O(h) time complexity involved in trie search operations.
We'll cover the following...
Search Algorithm
If we want to check whether a word is present in the trie or not, we need to keep tracing the path in the trie corresponding to the characters in word.
The logic isn’t too complex, but there are a few cases we need to take care of.
Case 1: Non-Existent Word
If we are searching for a word that doesn’t exist in the trie and is not a subset of any other word, by principle, we will find NULL before the last character of the word can be found.
For a better understanding, check out the illustration below:
Case 2: Word Exists as a Substring
This is the case where our word can be found as a substring of another word, but the isEndWord property for it has been set to false.
In the example below, we are searching for the word be. It is a subset of the already existing word bed, but the e node has not been ...