# Trie Search Word Element

In computer science, a trie (pronounced "try") is a tree-like data structure often used for efficient string manipulation tasks. The primary advantage of a trie is that it allows for fast searching, insertion, and deletion of strings. This post example focuses on implementing the search operation for a Trie data structure.

## Problem Statement

Given a Trie data structure containing various strings, the problem is to determine whether a specific word exists in the Trie or not.

## Example

Consider a Trie with the strings "cooky", "codify", "data", and "comedy" inserted into it. We want to search for the presence of the words "com" and "data" in the Trie.

## Idea to Solve

The solution involves traversing the Trie based on the characters of the search word. If at any point a character's corresponding child node is not present, the search fails. However, if we successfully traverse through the Trie following the characters of the search word and reach a node marked as the end of a string, then the search is successful.

## Pseudocode

``````search(text):
node = root
for each character in text:
index = character - 'a'
if node.children[index] is null:
return false
node = node.children[index]
if node is not null and node.end is true:
return true
else:
return false``````

## Algorithm Explanation

1. Start at the root node of the Trie.
2. Traverse through each character of the search text.
3. For each character, calculate the index by subtracting the ASCII value of 'a'.
4. If the child node at the calculated index is null, return false to indicate that the search text doesn't exist in the Trie.
5. If the child node is present, move to that node and continue the traversal.
6. After traversing all characters, check if the current node is not null and marks the end of a string. If both conditions are met, return true to indicate a successful search. Otherwise, return false.

## Code Solution

``````/*
C++ Program
Trie Search Word Element
*/
#include <iostream>

#include <string.h>
#define ALPHABETS 26
using namespace std;
class Node {
public:
bool end;
Node *children[ALPHABETS];
Node() {
this->end = false;
for (int i = 0; i < ALPHABETS; ++i) {
this->children[i] = NULL;
}
}
};
class Trie {

public:
Node *root;
Trie() {
this->root = new Node();
}
//Search given text is exist in tire
bool search(string text) {
int length = text.size();
int index = 0;
for (int level = 0; level < length; level++) {
index = text[level] - 'a';
return false;
}
}
return true;
} else {
return false;
}
}

void insert(string text) {
int size = text.size();
int index = 0;
int level = 0;
while (level < size) {
index = text[level] - 'a';
}
level++;
}
}
}

};
int main() {
Trie obj;
obj.insert("cooky");
obj.insert("codify");
obj.insert("data");
obj.insert("comedy");
string text = "com";
if (obj.search(text)) {
cout << "Exist : " << text << endl;
} else {
cout << "Not Exist : " << text << endl;
}
text = "data";
if (obj.search(text)) {
cout << "Exist : " << text << endl;
} else {
cout << "Not Exist : " << text << endl;
}
}```
```

#### Output

``````Not Exist : com
Exist : data
``````
``````/*
Java program
Trie Search Node Text
*/
class Node {
//Indicates end of string
public boolean end;

public Node[] children;

public Node(int size) {
end = false;
children = new Node[size];
}
}
public class Trie {
public int ALPHABETS = 26;

public Node root;

public Trie() {
root = new Node(ALPHABETS);
}
//Search given text is exist in tire
public boolean search(String text) {
//first get the length of text
int length = text.length();

//This variable are used to task find the index location of character
int index = 0;

//get the root node

for (int level = 0; level < length; level++) {
//Get the index
index = text.charAt(level) - 'a';

return false;
}

}
return true;
} else {
return false;
}
}
public void insert(String text) {
//first get the length of text
int length = text.length();

//This variable are used to task find the index location of character
int index = 0;

//get the root node

for (int level = 0; level < length; level++) {
//Get the index
index = text.charAt(level) - 'a';

//When need to add new Node
}

}
//indicates end of string
}
}
public static void main(String[] args) {
//Make object
Trie obj = new Trie();

obj.insert("cooky");
obj.insert("codify");
obj.insert("data");
obj.insert("comedy");

String text = "com";

if (obj.search(text)) {
System.out.println("Exist : " + text);
} else {
System.out.println("Not Exist : " + text);
}

text = "data";

if (obj.search(text)) {
System.out.println("Exist : " + text);
} else {
System.out.println("Not Exist : " + text);
}
}
}```
```

#### Output

``````Not Exist : com
Exist : data
``````
``````/*
C# program
Trie Search Node Text
*/
using System;
public class Node {
//Indicates end of string
public Boolean end;

public Node[] children;

public Node(int size) {
end = false;
children = new Node[size];
}
}
public class Trie {
private int ALPHABETS = 26;

public Node root;

public Trie() {
root = new Node(ALPHABETS);
}
//Search given text is exist in tire
public Boolean search(String text) {
//first get the.Length of text
int size = text.Length;

//This variable are used to task find the index location of character
int index = 0;

//get the root node

for (int level = 0; level < size; level++) {
//Get the index
index = text[level] - 'a';

return false;
}

}
return true;
} else {
return false;
}
}
public void insert(String text) {
//first get the.Length of text
int size = text.Length;

//This variable are used to task find the index location of character
int index = 0;

//get the root node

for (int level = 0; level < size; level++) {
//Get the index
index = text[level] - 'a';

//When need to add new Node
}

}
//indicates end of string
}
}
public static void Main(String[] args) {
//Make object
Trie obj = new Trie();

obj.insert("cooky");
obj.insert("codify");
obj.insert("data");
obj.insert("comedy");

String text = "com";

if (obj.search(text)) {
Console.WriteLine("Exist : " + text);
} else {
Console.WriteLine("Not Exist : " + text);
}

text = "data";

if (obj.search(text)) {
Console.WriteLine("Exist : " + text);
} else {
Console.WriteLine("Not Exist : " + text);
}
}
}```
```

#### Output

``````Not Exist : com
Exist : data
``````
``````#Python3 Program
#Trie Search Node Text
class Node :

def __init__(self, size) :
self.end = False
self.children = [None]*size

class Trie :

def __init__(self) :
self.ALPHABETS = 26
self.root = Node(self.ALPHABETS)

def search(self, text) :
size = len(text)
index = 0
level = 0
while (level < size) :
index = ord(text[level]) - ord('a')
return False

level += 1

return True
else :
return False

def insert(self, text) :
size = len(text)
index = 0
level = 0
while (level < size) :
index = ord(text[level]) - ord('a')

level += 1

def main() :
obj = Trie()
obj.insert("cooky")
obj.insert("codify")
obj.insert("data")
obj.insert("comedy")
text = "com"
if (obj.search(text)) :
print("Exist : ", text)
else :
print("Not Exist : ", text)

text = "data"
if (obj.search(text)) :
print("Exist : ", text)
else :
print("Not Exist : ", text)

if __name__ == "__main__":
main()```
```

#### Output

``````Not Exist : com
Exist : data
``````
``````#Ruby Program
#Trie Search Node Text
class Node
attr_accessor :end, :children
def initialize(size)
@end = false
@children = Array.new(size){nil}
end
end

class Trie
attr_accessor :ALPHABETS, :root
def initialize()
@ALPHABETS = 26
@root = Node.new(@ALPHABETS)
end
def search(text)
size = text.length
location = 0
level = 0
while (level < size)
location = text[level].ord-'a'.ord
return false
end
level += 1
end
return true
else
return false
end
end
def insert(text)
size = text.length
location = 0
level = 0
while (level < size)
location = text[level].ord-'a'.ord
end
level += 1
end
end
end
end
def main()
obj = Trie.new()
obj.insert("cooky")
obj.insert("codify")
obj.insert("data")
obj.insert("comedy")
text = "com"
if (obj.search(text))
print("Exist  :" + text+"\n")
else
print("Not Exist  :" + text+"\n")
end
text = "data"
if (obj.search(text))
print("Exist  :" + text+"\n")
else
print("Not Exist  :" + text+"\n")
end
end
main() ```
```

#### Output

``````Not Exist : com
Exist : data
``````
``````<?php
/*
Php Program
Trie Search Node Text
*/
class Node {
public \$end;
public \$children =[];

function __construct(\$size) {
\$this->end = false;
\$this->children = array_fill(0, \$size, null);
}
}
class Trie {
private \$ALPHABETS = 26;
public \$root;

function __construct() {
\$this->root = new Node(\$this->ALPHABETS);
}
public  function search(\$text) {
\$size = strlen(\$text);
\$index = 0;
\$level = 0;
while (\$level < \$size) {
\$index =  ord(\$text[\$level]) - ord('a');
return false;
}
\$level++;
}
return true;
} else {
return false;
}
}
public  function insert(\$text) {
\$size = strlen(\$text);
\$index = 0;
\$level = 0;
while (\$level < \$size) {
\$index =  ord(\$text[\$level]) - ord('a');
}
\$level++;
}
}
}

}

function main() {
\$obj = new Trie();
\$obj->insert("cooky");
\$obj->insert("codify");
\$obj->insert("data");
\$obj->insert("comedy");
\$text = "com";
if (\$obj->search(\$text)) {
echo "Exist : ". \$text."\n";
} else {
echo "Not Exist : ". \$text."\n";
}
\$text = "data";
if (\$obj->search(\$text)) {
echo "Exist : ". \$text."\n";
} else {
echo "Not Exist : ". \$text."\n";
}
}
main();```
```

#### Output

``````Not Exist : com
Exist : data
``````
``````/*
Node Js Program
Trie Search Node Text
*/
class Node {

constructor(size) {
this.end = false;
this.children = new Array(size).fill(null);
}
}
class Trie {

constructor() {
this.ALPHABETS = 26;
this.root = new Node(this.ALPHABETS);
}
search(text) {
var size = text.length;
var index = 0;
var level = 0;
while (level < size) {
index = text.charCodeAt(level) - 'a'.charCodeAt(0);
return false;
}
level++;
}
return true;
} else {
return false;
}
}
insert(text) {
var size = text.length;
var index = 0;
var level = 0;
while (level < size) {
index = text.charCodeAt(level) - 'a'.charCodeAt(0);
}
level++;
}
}
}
}
function main() {
var obj = new Trie();
obj.insert("cooky");
obj.insert("codify");
obj.insert("data");
obj.insert("comedy");
var text = "com";
if (obj.search(text)) {
console.log("Exist : " + text);
} else {
console.log("Not Exist : " + text);
}
text = "data";
if (obj.search(text)) {
console.log("Exist : " + text);
} else {
console.log("Not Exist : " + text);
}
}
main();```
```

#### Output

``````Not Exist : com
Exist : data
``````

## Time Complexity Analysis

• The `search` operation has a time complexity of O(L), where L is the length of the search word. This is because each character of the search word involves a constant time operation to traverse the corresponding node in the Trie.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.