Prefix Search in Trie

Contents

ProblemExamplesVisualizationSolutionAlgorithmCode

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❯

  1. Start from the root node of the Trie.
  2. 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.
  3. After traversing all characters, return true — at least one word in the Trie starts with the given prefix.

Code

JavaScript
class TrieNode {
  constructor() {
    this.children = {};
    this.is_end_of_word = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  insert(word) {
    let node = this.root;
    for (let char of word) {
      if (!node.children[char]) {
        node.children[char] = new TrieNode();
      }
      node = node.children[char];
    }
    node.is_end_of_word = true;
  }

  startsWith(prefix) {
    let node = this.root;
    for (let char of prefix) {
      if (!node.children[char]) {
        return false;
      }
      node = node.children[char];
    }
    return true;
  }
}

// Example usage:
const trie = new Trie();
trie.insert("apple");
trie.insert("app");
console.log(trie.startsWith("app"));  // true
console.log(trie.startsWith("apx"));   // false