Prefix Search in Trie

Problem Statement❯

Given a list of words inserted into a Trie, implement a function to check whether any of the words start with a given prefix. The function should return true if such a prefix exists, otherwise false.

Examples❯

Inserted Words	Search Prefix	Expected Result	Explanation
["apple", "banana", "grape"]	"app"	true	The prefix "app" matches the start of the word "apple".Visualization
["apple", "banana", "grape"]	"gr"	true	The prefix "gr" matches the start of the word "grape".Visualization
["apple", "banana", "grape"]	"car"	false	None of the words start with the prefix "car".Visualization
[]	"any"	false	No words are inserted into the Trie, so no prefix can be matched.Visualization
["cat", "cater", "car"]	"ca"	true	All words share the prefix "ca".Visualization
["one", "only", "once"]	""	true	Since every word starts with an empty prefix, we should return `true`.Visualization

Visualization Player

Solution❯

To solve the problem of Prefix Search in Trie, we need to determine if any word stored in the Trie starts with a given prefix. This is different from a full word search because we only care whether a word starts with the prefix — not whether a word matches the prefix entirely.

How we approach the problem

A Trie is a tree-like data structure that is particularly efficient for prefix-based queries. Each node in the Trie represents a character, and a path from the root to any node represents a prefix of some word(s).

When performing a prefix search:

We start from the root of the Trie.
We go through each character of the prefix one by one.
For each character, we check whether it exists as a child of the current node.
If any character is missing, we conclude that no word with that prefix exists in the Trie.
If we reach the end of the prefix successfully, it means at least one word in the Trie starts with the prefix.

Example:

Suppose the Trie contains: ["app", "apple", "bat", "ball"]

Prefix to search: "ap"
Start at root → Check for 'a' → Exists
Move to 'a' → Check for 'p' → Exists
All characters in the prefix found → Return true

Edge Cases

Case 1 - Empty prefix string

Description: The prefix string is an empty string: ""

Since every word starts with an empty prefix, we should return true.

Example:

Trie: ["a", "ab", "abc"]
Prefix: "" → Result: true

Case 2 - Prefix longer than any stored word

Description: The prefix is longer than any word in the Trie.

Traverse the Trie character by character.
If at any point the character is not found, return false.

Example:

Trie: ["do", "dog", "dot"]
Prefix: "dodge" → Result: false

For char 'o', there is no child 'd'. Prefix not present in the trie, hence returning false.

Case 3 - Prefix partially matches a word

Description: The prefix matches the start of a word but does not reach a full word.

We only care if the prefix matches a path in the Trie.
If the prefix exists in the Trie path, return true.

Example:

Trie: ["go", "gone", "golf"]
Prefix: "gol" → Result: true

Case 4 - Prefix not found at all

Description: The prefix has no matching characters in the Trie.

As soon as we find a character in the prefix that is not in the current node’s children, we return false.

Example:

Trie: ["cat", "car", "cart"]
Prefix: "dog" → Result: false

Root of the trie has only one child 'c'. First character in given prefix is 'd' and this is not there in the list of children of the root of trie. Therefore, return false.

Case 5 - Multiple words start with the same prefix

Description: The prefix matches the beginning of several words.

Even if one word starts with the prefix, return true.
Don’t worry about counting how many words — just whether any word matches.

Example:

Trie: ["star", "start", "stark"]
Prefix: "sta" → Result: true

Case 6 - Trie is empty

Description: No words are present in the Trie at all.

If Trie is empty, any prefix will return false.

Example:

Trie: []
Prefix: "a" → Result: false

Algorithm Steps❯

Start from the root node of the Trie.
For each character in the input prefix:
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 — no word in the Trie starts with this prefix.
After traversing all characters, return true — at least one word in the Trie starts with the given prefix.

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 startsWith(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

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

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(m)	In the best case, all characters of the prefix are found without branching into deeper nodes. The algorithm performs a single traversal of m characters (length of the prefix).
Average Case	O(m)	Regardless of Trie shape or number of words, the algorithm checks each of the m characters once while traversing the prefix path.
Worst Case	O(m)	Even in the worst case, the algorithm must examine each of the m characters in the prefix sequentially from the root node. No backtracking or revisits occur.

Space Complexity❯

O(1)

Explanation: The search uses a constant amount of extra space (just a pointer to traverse the Trie), as no additional data structures are created during traversal.

⬅ Previous TopicInsert Word in Trie

Next Topic ⮕Delete Word from Trie

Prefix Search in Trie

Contents

Problem Statement❯

Examples❯

Visualization Player

Solution❯

How we approach the problem

Example:

Edge Cases

Case 1 - Empty prefix string

Example:

Case 2 - Prefix longer than any stored word

Example:

Case 3 - Prefix partially matches a word

Example:

Case 4 - Prefix not found at all

Example:

Case 5 - Multiple words start with the same prefix

Example:

Case 6 - Trie is empty

Example:

Algorithm Steps❯

Code

Time Complexity❯

Space Complexity❯

Welcome to ProgramGuru

Player Settings