Search Word in Trie

Problem Statement❯

Given a list of words inserted into a Trie, check whether a given search word exists in the Trie. The function should return true if the word is found and fully matches a word previously inserted, otherwise return false.

Examples❯

Inserted Words	Search Word	Expected Result	Explanation
["apple", "banana", "grape"]	"banana"	true	"banana" was inserted and fully matches, so the search returns true. Visualization
["apple", "banana", "grape"]	"ban"	false	"ban" is a prefix of "banana" but not a complete word in the Trie. Visualization
[]	"apple"	false	No words are inserted, so the search will always return false. Visualization
["cat", "dog"]	""	false	An empty search string is not considered a valid word in the Trie.Visualization
["one", "only", "once"]	"only"	true	The word "only" exactly matches a word in the Trie. Visualization
["one", "only", "once"]	"on"	false	"on" is a prefix shared by multiple words but is not a full word in the Trie. Visualization

Visualization Player

Solution❯

To determine whether a word exists in a Trie, we perform a character-by-character traversal starting from the root node. For each character in the search word, we check if the character exists in the current node's children. If it does, we move to that child node and continue. If we encounter a character that doesn't exist in the Trie at any point, we know immediately that the word does not exist, so we return false.

However, reaching the end of the word isn't enough — we must also ensure that the last character leads us to a node that is explicitly marked as the end of a valid word. If not, then the word is only a prefix of some longer word and should still return false.

Let’s consider some cases:

Normal case:
If we insert ["one", "only", "once"] and search for "once", we follow each letter until the end and confirm it ends at a valid word node. So, return true. Visualization
Prefix case:
Searching for "on" in the same Trie reaches valid characters but doesn’t hit an end-of-word node, so we return false. Visualization
Empty Trie: If no words are inserted, any search word will return false because the Trie is completely empty.
Empty string search: Searching with an empty string is often considered invalid unless explicitly allowed. In most Trie implementations, this will return false.

This operation is highly efficient — its time complexity is O(m), where m is the length of the search word, making it much faster than linear search for large sets of words.

Algorithm Steps❯

Start from the root node of the Trie.
For each character in the input word:
1. Check if the character exists in the current node's children map.
2. If it does, move to the corresponding child node.
3. If it does not, return false — the word is not present in the Trie.
After traversing all characters, check if the current node is marked as the end of a valid word.
Return true only if the final node signifies the end of a word; otherwise, return false.

Code

Python

Java

JavaScript

C++

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end_of_word

# Example usage
trie = Trie()
trie.insert("apple")
trie.insert("app")
print(trie.search("apple"))  # True
print(trie.search("appl"))   # False

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(k)	The algorithm must traverse each character of the input word (of length k) even if all characters are found immediately in the Trie. Therefore, best case is linear in the length of the word.
Average Case	O(k)	On average, the algorithm traverses all k characters of the word to determine if it exists in the Trie. Each character check takes constant time using a hash map or array lookup.
Worst Case	O(k)	In the worst case, the word is either not present or only partially present, but the algorithm still examines all k characters before failing. Each character requires a constant-time check in the children map.

Space Complexity❯

O(1)

Explanation: The search operation uses only a constant amount of extra space for pointers or references during traversal. No additional data structures are created proportional to input size.

⬅ Previous TopicStrongly Connected Components using Kosaraju's Algorithm

Next Topic ⮕Insert Word in Trie

Search Word in Trie

Contents

Problem Statement❯

Examples❯

Visualization Player

Solution❯

Normal case:

Prefix case:

Algorithm Steps❯

Code

Time Complexity❯

Space Complexity❯

Welcome to ProgramGuru

Player Settings