AlgoDaily - Trie Data Structure

Home > Advanced data structures and algorithms > Advanced data structures and algorithms > Trie Data Structure

To search for a word in a trie, follow these steps:

Start from the root node and initialize a pointer current to track the current node.
Iterate through each character in the word.
Check if the current node contains a link for the character. If not, the word is not present in the trie.
Update the current pointer to the next node.
Repeat steps 3-4 for all characters in the word.
After iterating through all characters, check if the current node marks the end of a word. If yes, the word is present in the trie. Otherwise, the word is not present.

Here is an example implementation of the search method in the Trie class:

xxxxxxxxxx
 
class Trie {
​
    // ... other methods
​
    public boolean search(String word) {
        TrieNode current = root;
​
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            TrieNode node = current.getChildren().get(ch);
​
            // If the current node doesn't contain a link for the character,
            // the word is not present in the trie
            if (node == null) {
                return false;
            }
​
            current = node;
        }
​
        // After iterating through all characters,
        // the word is present if the current node marks the end of a word
        return current.isEndOfWord();
    }
​
    // ... other methods
​
}

Programming Categories

Popular Lessons