Search Word in Trie - Visualization

Tries

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

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

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❯

  1. Start from the root node of the Trie.
  2. 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.
  3. After traversing all characters, check if the current node is marked as the end of a valid word.
  4. Return true only if the final node signifies the end of a word; otherwise, return false.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define ALPHABET_SIZE 26

typedef struct TrieNode {
    struct TrieNode *children[ALPHABET_SIZE];
    bool isEndOfWord;
} TrieNode;

TrieNode* createNode() {
    TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));
    node->isEndOfWord = false;
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        node->children[i] = NULL;
    }
    return node;
}

void insert(TrieNode* root, const char* word) {
    TrieNode* node = root;
    while (*word) {
        int index = *word - 'a';
        if (!node->children[index]) {
            node->children[index] = createNode();
        }
        node = node->children[index];
        word++;
    }
    node->isEndOfWord = true;
}

bool search(TrieNode* root, const char* word) {
    TrieNode* node = root;
    while (*word) {
        int index = *word - 'a';
        if (!node->children[index]) {
            return false;
        }
        node = node->children[index];
        word++;
    }
    return node->isEndOfWord;
}

int main() {
    TrieNode* root = createNode();
    insert(root, "apple");
    insert(root, "app");
    printf("%s\n", search(root, "apple") ? "true" : "false"); // true
    printf("%s\n", search(root, "appl") ? "true" : "false");  // false
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(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 CaseO(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 CaseO(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.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...