Trie
Search

⬅ Previous Topic

Strongly Connected Components using Kosaraju's Algorithm

Topic Contents

Problem Examples Solution Visualization Algorithm Code

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.
["cat", "dog"]	""	false	An empty search string is not considered a valid word in the Trie.
["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

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 ["apple", "banana", "grape"] and search for "banana", we follow each letter until the end and confirm it ends at a valid word node. So, return true. Visualization
Prefix case: Searching for "ban" 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.

Visualization

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

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;
  }

  search(word) {
    let node = this.root;
    for (let char of word) {
      if (!node.children[char]) {
        return false;
      }
      node = node.children[char];
    }
    return node.is_end_of_word;
  }
}

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

Overview of Techniques14
❯

Sorting6
❯

Arrays32
❯

Arrays - Binary Search28
❯

Strings18
❯

Matrix3
❯

Matrix - Binary Search5
❯

Binary Trees36
❯

Binary Search Trees14
❯

Graphs46
❯

Tries1
❯

Trie
Search

Problem Statement

Examples❯

Solution❯

Visualization

Algorithm Steps

Code

Support ProgramGuru.org❯

TrieSearch

Problem Statement

Examples❯

Solution❯

Visualization

Algorithm Steps

Code

Welcome to ProgramGuru

Support ProgramGuru.org❯

Trie
Search