Posted on by Kalkicode
Code Tree

# Find a longest length word in Trie

Trie, also known as a prefix tree, is a data structure used for efficiently storing and searching a large collection of strings. In this article, we'll explore the problem of finding the longest word stored in a Trie data structure. We'll provide a detailed explanation, step-by-step approach, pseudocode, and algorithm, along with an example and the expected output.

## Problem Statement

Given a Trie containing a set of words, we are tasked with finding the longest word present in the Trie.

## Example Scenario

Let's consider a Trie containing the following words:

1. cool
2. coder
3. confirm
4. child

We want to find the longest word in this Trie.

## Idea to Solve

To solve this problem, we can traverse the Trie in a depth-first manner while keeping track of the longest word encountered so far. We'll explore each branch of the Trie, and at each step, we'll consider the possibilities of extending the current longest word.

## Pseudocode

``````class TrieNode:
boolean isEndOfWord
TrieNode[ALPHABETS] children

class Trie:
TrieNode root

insert(word):
node = root
for char in word:
index = char - 'a'
if node.children[index] is None:
node.children[index] = new TrieNode()
node = node.children[index]
node.isEndOfWord = true

longestWord(node, currentWord, longestSoFar):
if node is not None:
for i in 0 to ALPHABETS - 1:
if node.children[i] is not None:
newWord = currentWord + character(i)
longestWord(node.children[i], newWord, longestSoFar)

if currentWord.length > longestSoFar.length:
longestSoFar = currentWord

return longestSoFar``````

## Algorithm Explanation

1. Initialize a Trie data structure with its root.
2. Insert the given words into the Trie using the `insert` function.
3. Initialize a variable `longestSoFar` to store the longest word encountered.
4. Define the `longestWord` function that performs a depth-first traversal of the Trie:
• For each child of the current node, recursively call the `longestWord` function.
• During the traversal, build the `currentWord` by appending characters encountered along the path.
• If the length of the `currentWord` is greater than the length of `longestSoFar`, update `longestSoFar`.
5. In the `main` function, create a Trie object and insert the given words.
6. Call the `longestWord` function starting from the root of the Trie and with an empty `currentWord`.
7. Print the value of `longestSoFar`.

## Code Solution

``````/*
C++ program
Find a longest length word in Trie
*/
#include <iostream>

using namespace std;
#define ALPHABETS 26
//This is tire tree node
class Node
{
public:
//Indicates stop of string
bool stop;
Node *children[ALPHABETS];
Node()
{
this->stop = false;
for (int i = 0; i < ALPHABETS; ++i)
{
this->children[i] = NULL;
}
}
};
class Trie
{
public: Node *root;
Trie()
{
this->root = new Node();
}
//This function are add new element
void insert(string text)
{
//first get the length of text
int length = text.size();
//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[level] - 'a';
{
//When need to add new Node
}
}
{
//indicates stop of string
}
}
//This function are finding largest word length string in given tire tree
{
string text = about, temp = "";
if (root != NULL)
{
for (int i = 0; i < ALPHABETS; i++)
{
temp = "";
if (root->children[i] != NULL)
{
temp = longest_word(root->children[i], about + ((char)(i + 97)));
}
if (temp.size() > text.size())
{
text = temp;
}
}
}
{
return text;
}
else
{
}
}
};
int main()
{
//Make object of Tree
Trie obj = Trie();
//Add following nodes in trie tree
obj.insert("cool");
obj.insert("coder");
obj.insert("confirm");
obj.insert("child");
cout << "Longest word is : " << obj.longest_word(obj.root, "");
return 0;
}``````

#### Output

``Longest word is : confirm``
``````/*
Java program
Find a longest length word in Trie
*/
//This is tire tree node
class Node
{
//Indicates stop of string
public boolean stop;
public Node[] children;
public Node(int size)
{
this.stop = false;
this.children = new Node[size];
}
}
class Trie
{
public int alphabets;
public Node root;
public Trie()
{
this.alphabets = 26;
this.root = new Node(this.alphabets);
}
//This function are add new element
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 stop of string
}
}
//This function are finding largest word length string in given tire tree
public String longest_word(Node root, String about)
{
String text = about, temp = "";
if (root != null)
{
for (int i = 0; i < this.alphabets; i++)
{
temp = "";
if (root.children[i] != null)
{
temp = longest_word(root.children[i], about + ((char)(i + 97)));
}
if (temp.length() > text.length())
{
text = temp;
}
}
}
{
return text;
}
else
{
}
}
public static void main(String[] args)
{
//Make object of Tree
Trie obj = new Trie();
//Add following nodes in trie tree
obj.insert("cool");
obj.insert("coder");
obj.insert("confirm");
obj.insert("child");
System.out.println("Longest word is : " + obj.longest_word(obj.root, ""));
}
}``````

#### Output

``Longest word is : confirm``
``````/*
C# program
Find a longest length word in Trie
*/
//Include namespace system
using System;
//This is tire tree node
public class Node
{
//Indicates stop of string
public Boolean stop;
public Node[] children;
public Node(int size)
{
this.stop = false;
this.children = new Node[size];
}
}
class Trie
{
public int alphabets;
public Node root;
public Trie()
{
this.alphabets = 26;
this.root = new Node(this.alphabets);
}
//This function are add new element
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[level] - 'a';
{
//When need to add new Node
}
}
{
//indicates stop of string
}
}
//This function are finding largest word length string in given tire tree
public String longest_word(Node root, String about)
{
String text = about, temp = "";
if (root != null)
{
for (int i = 0; i < this.alphabets; i++)
{
temp = "";
if (root.children[i] != null)
{
temp = longest_word(root.children[i], about + ((char)(i + 97)));
}
if (temp.Length > text.Length)
{
text = temp;
}
}
}
{
return text;
}
else
{
}
}
public static void Main(String[] args)
{
//Make object of Tree
Trie obj = new Trie();
//Add following nodes in trie tree
obj.insert("cool");
obj.insert("coder");
obj.insert("confirm");
obj.insert("child");
Console.WriteLine("Longest word is : " + obj.longest_word(obj.root, ""));
}
}``````

#### Output

``Longest word is : confirm``
``````#
#   Python 3 program
#   Find a longest length word in Trie

# This is tire tree node
class Node :
# Indicates stop of string

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

class Trie :

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

# This function are add new element
def insert(self, text) :
# first get the length of text
length = len(text)
# This variable are used to task find the index location of character
index = 0
# get the root node
level = 0
while (level < length) :
# Get the index
index = ord(text[level]) - ord('a')

# When need to add new Node

level += 1

# indicates stop of string

# This function are finding largest word length string in given tire tree
temp = ""
if (root != None) :
i = 0
while (i < self.alphabets) :
temp = ""
if (root.children[i] != None) :
temp = self.longest_word(root.children[i], about + ((chr(i + 97))))

if (len(temp) > len(text)) :
text = temp

i += 1

return text
else :

def main() :
# Make object of Tree
obj = Trie()
# Add following nodes in trie tree
obj.insert("cool")
obj.insert("coder")
obj.insert("confirm")
obj.insert("child")

print("Longest word is : ", obj.longest_word(obj.root, ""), end = "")

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

#### Output

``Longest word is :  confirm``
``````#   Ruby program
#   Find a longest length word in Trie

# This is tire tree node
class Node

# Define the accessor and reader of class Node
attr_accessor :stop, :children

# Indicates stop of string
def initialize(size)

self.stop = false
self.children = Array.new(size){nil}
end
end
class Trie

# Define the accessor and reader of class Trie
attr_accessor :alphabets, :root

def initialize()

self.alphabets = 26
self.root = Node.new(self.alphabets)
end
# This function are add new element
def insert(text)

# first get the length of text
length = text.length()
# This variable are used to task find the index location of character
index = 0
# get the root node
level = 0
while (level < length)

# Get the index
index = (text[level]).ord - ('a').ord

# When need to add new Node
end
level += 1
end

# indicates stop of string
end
end
# This function are finding largest word length string in given tire tree

temp = ""
if (root != nil)

i = 0
while (i < self.alphabets)

temp = ""
if (root.children[i] != nil)

temp = self.longest_word(root.children[i], about + (((i + 97)).chr))
end
if (temp.length() > text.length())

text = temp
end
i += 1
end
end

return text
else

end
end
end
def main()

# Make object of Tree
obj = Trie.new()
# Add following nodes in trie tree
obj.insert("cool")
obj.insert("coder")
obj.insert("confirm")
obj.insert("child")
print("Longest word is : ", obj.longest_word(obj.root, ""))
end
main()``````

#### Output

``Longest word is : confirm``
``````/*
Scala program
Find a longest length word in Trie
*/
//This is tire tree node
class Node(var stop: Boolean,
var children: Array[Node])
{
def this(size: Int)
{
this(false, Array.fill[Node](size)(null));
}
}
class Trie(var alphabets: Int,
var root: Node)
{
def this()
{
this(26, new Node(26));
}
//This function are add new element
def insert(text: String): Unit = {
//first get the length of text
var length: Int = text.length();
//This variable are used to task find the index location of character
var index: Int = 0;
//get the root node
var level: Int = 0;
while (level < length)
{
//Get the index
index = text(level) - 'a';
{
//When need to add new Node
}
level += 1;
}
{
//indicates stop of string
}
}
//This function are finding largest word length string in given tire tree
def longest_word(root: Node, about: String): String = {
var temp: String = "";
if (root != null)
{
var i: Int = 0;
while (i < this.alphabets)
{
temp = "";
if (root.children(i) != null)
{
temp = longest_word(root.children(i), about + ((i + 97).toChar));
}
if (temp.length() > text.length())
{
text = temp;
}
i += 1;
}
}
{
return text;
}
else
{
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
//Make object of Tree
var obj: Trie = new Trie();
//Add following nodes in trie tree
obj.insert("cool");
obj.insert("coder");
obj.insert("confirm");
obj.insert("child");
print("Longest word is : " + obj.longest_word(obj.root, ""));
}
}``````

#### Output

``Longest word is : confirm``
``````/*
Swift program
Find a longest length word in Trie
*/
//This is tire tree node
class Node
{
//Indicates stop of string
var stop: Bool;
var children: [Node? ] = [Node]();
init(_ size: Int)
{
self.stop = false;
var i = 0;
while (i < size)
{
self.children.append(nil);
i += 1;
}
}
}
class Trie
{
var alphabets: Int;
var root: Node? ;
init()
{
self.alphabets = 26;
self.root = Node(self.alphabets);
}
//This function are add new element
func insert(_ data: String)
{
//first get the length of text
let length: Int = data.count;
let text = Array(data);
//This variable are used to task find the index location of character
var index: Int = 0;
//get the root node
var level: Int = 0;
while (level < length)
{
//Get the index
index = Int(UnicodeScalar(String(text[level]))!.value -
UnicodeScalar("a")!.value);
{
//When need to add new Node
}
level += 1;
}
{
//indicates stop of string
}
}
//This function are finding largest word length string in given tire tree
func longest_word(_ root: Node? , _ about : String) -> String
{
var temp: String = "";
if (root != nil)
{
var i: Int = 0;
while (i < self.alphabets)
{
temp = "";
if (root!.children[i] != nil)
{
temp = self.longest_word(root!.children[i], about + (String(UnicodeScalar(UInt8((i + 97))))));
}
if (temp.count > text.count)
{
text = temp;
}
i += 1;
}
}
{
return text;
}
else
{
}
}
}
func main()
{
//Make object of Tree
let obj: Trie = Trie();
//Add following nodes in trie tree
obj.insert("cool");
obj.insert("coder");
obj.insert("confirm");
obj.insert("child");
print("Longest word is : ", obj.longest_word(obj.root, ""), terminator: "");
}
main();``````

#### Output

``Longest word is :  confirm``
``````<?php
/*
Php program
Find a longest length word in Trie
*/
//This is tire tree node
class Node
{
//Indicates stop of string
public \$stop;
public \$children;

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

function __construct()
{
\$this->alphabets = 26;
\$this->root = new Node(\$this->alphabets);
}
//This function are add new element
public  function insert(\$text)
{
//first get the length of text
\$length = strlen(\$text);
//This variable are used to task find the index location of character
\$index = 0;
//get the root node
for (\$level = 0; \$level < \$length; \$level++)
{
//Get the index
\$index = ord(\$text[\$level]) - ord('a');
{
//When need to add new Node
}
}
{
//indicates stop of string
}
}
//This function are finding largest word length string in given tire tree
{
\$temp = "";
if (\$root != null)
{
for (\$i = 0; \$i < \$this->alphabets; \$i++)
{
\$temp = "";
if (\$root->children[\$i] != null)
{
\$temp = \$this->longest_word(\$root->children[\$i], \$about . chr(((\$i + 97))));
}
if (strlen(\$temp) > strlen(\$text))
{
\$text = \$temp;
}
}
}
{
return \$text;
}
else
{
}
}
}

function main()
{
//Make object of Tree
\$obj = new Trie();
//Add following nodes in trie tree
\$obj->insert("cool");
\$obj->insert("coder");
\$obj->insert("confirm");
\$obj->insert("child");
echo "Longest word is : ". \$obj->longest_word(\$obj->root, "");
}
main();``````

#### Output

``Longest word is : confirm``
``````/*
Node Js program
Find a longest length word in Trie
*/
//This is tire tree node
class Node
{
constructor(size)
{
this.stop = false;
this.children = Array(size).fill(null);
}
}
class Trie
{
constructor()
{
this.alphabets = 26;
this.root = new Node(this.alphabets);
}
//This function are add new element
insert(text)
{
//first get the length of text
var length = text.length;
//This variable are used to task find the index location of character
var index = 0;
//get the root node
for (var level = 0; level < length; level++)
{
//Get the index
index = text.charCodeAt(level) - 'a'.charCodeAt(0);
{
//When need to add new Node
}
}
{
//indicates stop of string
}
}
//This function are finding largest word length string in given tire tree
{
var temp = "";
if (root != null)
{
for (var i = 0; i < this.alphabets; i++)
{
temp = "";
if (root.children[i] != null)
{
temp = this.longest_word(root.children[i], about + String.fromCharCode(((i + 97))));
}
if (temp.length > text.length)
{
text = temp;
}
}
}
{
return text;
}
else
{
}
}
}

function main()
{
//Make object of Tree
var obj = new Trie();
//Add following nodes in trie tree
obj.insert("cool");
obj.insert("coder");
obj.insert("confirm");
obj.insert("child");
process.stdout.write("Longest word is : " + obj.longest_word(obj.root, ""));
}
main();``````

#### Output

``Longest word is : confirm``

## Time Complexity

The time complexity of inserting a word into the Trie is O(word_length), and the time complexity of the `longestWord` function is O(N), where N is the total number of characters in the Trie. Hence, the overall time complexity of the solution is O(N).

## 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.

Categories
Relative Post