Vultr DocsLatest Content

Implement Trie (Prefix Tree)

Updated on 03 June, 2025
Implement Trie (Prefix Tree) header image

Problem Statement

A trie, also known as a prefix tree, is a specialized tree-like data structure that facilitates the storage and retrieval of strings in a way that keys can be searched for by their prefixes. This characteristic makes tries an ideal solution for functionalities such as autocomplete systems and spellcheckers.

Implement a Trie class with the following functionalities:

  • Trie(): Initializes the trie.
  • void insert(String word): Inserts the string word into the trie.
  • boolean search(String word): Returns true if the word exists in the trie, otherwise returns false.
  • boolean startsWith(String prefix): Returns true if any word in the trie starts with the given prefix, otherwise returns false.

Examples

Example 1

Input:

["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]

Output:

[null, null, true, false, true, null, true]

Explanation:

Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");       // returns true
trie.search("app");         // returns false
trie.startsWith("app");     // returns true
trie.insert("app");
trie.search("app");         // returns true

Constraints

  • 1 <= word.length, prefix.length <= 2000
  • word and prefix consist only of lowercase English letters.
  • At most 3 * 10^4 calls in total will be made to insert, search, and startsWith.

Approach and Intuition

Tries offer efficient word and prefix lookups by decomposing strings into character-level nodes:

  1. Initialization:

    • The root node is created. Each node maintains a character-to-child mapping and an end-of-word flag.

  2. Insertion:

    • For each character in word, traverse or create a child node.
    • After the last character, mark the final node as an end node.

  3. Search:

    • Traverse through each character of word.
    • If the full path exists and ends at a word marker, return true; otherwise, return false.

  4. Prefix Check:

    • Traverse through the prefix characters.
    • If the path exists regardless of the word-end marker, return true; otherwise, return false.

This character-by-character approach ensures O(L) time complexity for each operation, where L is the length of the input string. It’s ideal for high-frequency word lookups and incremental prefix matching.

Solutions

  • C++
  • Java
  • Python
cpp 
class Trie {
    
    bool hasPrefix(const string& prefix) {
        TrieNode* currentNode = searchPrefix(prefix);
        return currentNode != nullptr;
    }
}

The solution implements a basic structure of a trie (prefix tree) in C++. The provided function hasPrefix checks if a particular prefix is present in the trie, utilizing the searchPrefix method.

  • hasPrefix is a boolean function that takes a prefix string as an argument.
  • It uses a TrieNode* pointer, currentNode, to navigate through the trie starting from the root.
  • The searchPrefix helper function searches through the trie nodes to find the last node of the prefix.
  • If currentNode returns a non-null value, it indicates that the prefix exists in the trie; otherwise, the prefix does not exist.

This method efficiently checks for the existence of a prefix within the trie, leveraging the nested structure of the trie to reduce both time and space complexity compared to other data structures such as hash tables or balanced trees.

java 
class Trie {

    // Check if any word starts with a specific prefix in the trie.
    public boolean hasPrefix(String prefix) {
        TrieNode current = searchPrefix(prefix);
        return current != null;
    }
}

In the provided Java solution for implementing a basic functionality of a Trie (Prefix Tree), the focus is on checking if any word starts with a given prefix. This functionality is crucial for various applications such as autocomplete systems or spell checkers. The hasPrefix method utilizes another method searchPrefix, which isn't included in the provided snippet but is typically used to navigate through the Trie based on the characters of the prefix. If searchPrefix returns a non-null result, it implies that the Trie has at least one word starting with the specified prefix. This approach is efficient for prefix checks in a collection of strings.

python 
class Trie:

    def __init__(self):
        self.start_node = TrieNode()

    def prefix_exists(self, prefix: str) -> bool:
        current_node = self._search_prefix(prefix)
        return current_node is not None

Implement a Trie (Prefix Tree) in Python to efficiently store and search for string prefixes. The provided code includes a class Trie with methods for initialization and checking if a prefix exists within the nodes.

  • The __init__ method initializes the Trie with a starting node, created as an instance of TrieNode.
  • The prefix_exists method takes a string prefix as input and returns a boolean value indicating whether that prefix exists in the Trie. It leverages the helper method _search_prefix to traverse through each character of the prefix and check against existing Trie nodes.

To fully utilize the Trie class for operations such as insertions and extensive searches, consider implementing additional methods:

  • insert to add words to the Trie,
  • search to verify complete word presence, and
  • _search_prefix method to aid in prefix searches by returning the final node in the prefix chain or None if not found.

Follow these guidelines to ensure that your code effectively manages prefix operations, which are crucial for applications like autocomplete, spell-checkers, and other dictionary-based solutions.

Comments

No comments yet.