Searching in Trie Data Structure
Search operation in Trie is performed in a similar way as the insertion operation but the only difference is that whenever we find that the array of pointers in curr node does not point to the current character of the word then return false instead of creating a new node for that current character of the word.
This operation is used to search whether a string is present in the Trie data structure or not. There are two search approaches in the Trie data structure.
- Find whether the given word exists in Trie.
- Find whether any word that starts with the given prefix exists in Trie.
There is a similar search pattern in both approaches. The first step in searching a given word in Trie is to convert the word to characters and then compare every character with the trie node from the root node. If the current character is present in the node, move forward to its children. Repeat this process until all characters are found.
2.1 Searching Prefix in Trie Data Structure:
Search for the prefix “an” in the Trie Data Structure.
Search for the prefix “an” in Trie
Implementation of Prefix Search in Trie data structure:
bool isPrefixExist(TrieNode* root, string& key)
{
// Initialize the currentNode pointer
// with the root node
TrieNode* currentNode = root;
// Iterate across the length of the string
for (auto c : key) {
// Check if the node exist for the current
// character in the Trie.
if (currentNode->childNode[c - 'a'] == NULL) {
// Given word as a prefix does not exist in Trie
return false;
}
// Move the currentNode pointer to the already
// existing node for current character.
currentNode = currentNode->childNode[c - 'a'];
}
// Prefix exist in the Trie
return true;
}
public boolean isPrefixExist(TrieNode root, String key) {
// Initialize the currentNode pointer
// with the root node
TrieNode currentNode = root;
// Iterate across the length of the string
for (char c : key.toCharArray()) {
// Check if the node exist for the current
// character in the Trie.
if (currentNode.childNode[c - 'a'] == null) {
// Given word as a prefix does not exist in Trie
return false;
}
// Move the currentNode pointer to the already
// existing node for current character.
currentNode = currentNode.childNode[c - 'a'];
}
// Prefix exist in the Trie
return true;
}
def is_prefix_exist(root, key):
# Initialize the currentNode pointer
# with the root node
current_node = root
# Iterate across the length of the string
for c in key:
# Check if the node exist for the current
# character in the Trie.
if current_node.child_node[ord(c) - ord('a')] is None:
# Given word as a prefix does not exist in Trie
return False
# Move the currentNode pointer to the already
# existing node for current character.
current_node = current_node.child_node[ord(c) - ord('a')]
# Prefix exist in the Trie
return True
public bool isPrefixExist(TrieNode root, string key)
{
// Initialize the currentNode pointer
// with the root node
TrieNode currentNode = root;
// Iterate across the length of the string
foreach (char c in key)
{
// Check if the node exist for the current
// character in the Trie.
if (currentNode.childNode[c - 'a'] == null)
{
// Given word as a prefix does not exist in Trie
return false;
}
// Move the currentNode pointer to the already
// existing node for current character.
currentNode = currentNode.childNode[c - 'a'];
}
// Prefix exist in the Trie
return true;
}
function isPrefixExist(root, key) {
// Initialize the currentNode pointer with the root node
let currentNode = root;
// Iterate across the length of the string
for (let c of key) {
// Check if the node exist for the current character in the Trie.
if (currentNode.childNode[c.charCodeAt(0) - 'a'.charCodeAt(0)] === null) {
// Given word as a prefix does not exist in Trie
return false;
}
// Move the currentNode pointer to the already existing node for current character.
currentNode = currentNode.childNode[c.charCodeAt(0) - 'a'.charCodeAt(0)];
}
// Prefix exist in the Trie
return true;
}
2.2 Searching Complete word in Trie Data Structure:
It is similar to prefix search but additionally, we have to check if the word is ending at the last character of the word or not.
Search “dad” in the Trie data structure
Implementation of Search in Trie data structure:
bool search_key(TrieNode* root, string& key)
{
// Initialize the currentNode pointer
// with the root node
TrieNode* currentNode = root;
// Iterate across the length of the string
for (auto c : key) {
// Check if the node exist for the current
// character in the Trie.
if (currentNode->childNode[c - 'a'] == NULL) {
// Given word does not exist in Trie
return false;
}
// Move the currentNode pointer to the already
// existing node for current character.
currentNode = currentNode->childNode[c - 'a'];
}
return (currentNode->wordCount > 0);
}
// Returns true if key presents in trie, else false
static boolean search(TrieNode root, String key)
{
// Initialize the currentNode
// with the root node
TrieNode currentNode = root;
for (int i = 0; i < key.length(); i++) {
int index = key.charAt(i) - 'a';
// Check if the node exist for the current
// character in the Trie.
if (currentNode.childNode[index] == null)
return false;
// Move the currentNode to the already
// existing node for current character.
currentNode = currentNode.childNode[index];
}
return (currentNode.isEndOfWord);
}
def search_key(root, key):
# Initialize the currentNode pointer with the root node
currentNode = root
# Iterate across the length of the string
for c in key:
# Check if the node exist for the current character in the Trie
if currentNode.childNode[ord(c) - ord('a')] is None:
# Given word does not exist in Trie
return False
# Move the currentNode pointer to the already existing node for current character
currentNode = currentNode.childNode[ord(c) - ord('a')]
# Return if the wordCount is greater than 0
return currentNode.wordCount > 0
public bool SearchKey(TrieNode root, string key)
{
// Initialize the currentNode pointer with the root node
TrieNode currentNode = root;
// Iterate across the length of the string
foreach (char c in key)
{
// Check if the node exist for the current character in the Trie
if (currentNode.childNode[c - 'a'] == null)
{
// Given word does not exist in Trie
return false;
}
// Move the currentNode pointer to the already existing node for current character
currentNode = currentNode.childNode[c - 'a'];
}
// Return if the wordCount is greater than 0
return currentNode.wordCount > 0;
}
//This code is contributed by shivamsharma215
function searchKey(root, key) {
let currentNode = root;
for (let c of key) {
if (!currentNode.childNode[c.charCodeAt(0) - 'a'.charCodeAt(0)]) {
return false;
}
currentNode = currentNode.childNode[c.charCodeAt(0) - 'a'.charCodeAt(0)];
}
return currentNode.wordCount > 0;
}
Trie Data Structure Tutorial
The trie data structure, also known as a prefix tree, is a tree-like data structure used for efficient retrieval of key-value pairs. It is commonly used for implementing dictionaries and autocomplete features, making it a fundamental component in many search algorithms. In this article, we will explore all about Trie data structures in detail.
Trie Data Structure
Table of Content
- What is Trie Data Structure?
- What is need of Trie Data Structure?
- Advantages of Trie Data Structure over a Hash Table
- Properties of a Trie Data Structure
- How does Trie Data Structure work?
- Representation of Trie Node
- Basic Operations on Trie Data Structure
- Insertion in Trie Data Structure
- Searching in Trie Data Structure
- Deletion in Trie Data Structure
- Implement Trie Data Structure?
- Complexity Analysis of Trie Data Structure
- Applications of Trie data structure
- Advantages of Trie data structure
- Disadvantages of Trie data structure
- Top Interview problems on Trie data structure