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 header file
#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
		Node *head = this->root;
		for (int level = 0; level < length; level++)
		{
			//Get the index
			index = text[level] - 'a';
			if (head->children[index] == NULL)
			{
				//When need to add new Node
				head->children[index] = new Node();
			}
			head = head->children[index];
		}
		if (head != NULL)
		{
			//indicates stop of string
			head->stop = true;
		}
	}
	//This function are finding largest word length string in given tire tree
	string longest_word(Node *root, string about)
	{
		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;
				}
			}
		}
		if (text.size() > about.size())
		{
			return text;
		}
		else
		{
			return about;
		}
	}
};
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
		Node head = root;
		for (int level = 0; level < length; level++)
		{
			//Get the index
			index = text.charAt(level) - 'a';
			if (head.children[index] == null)
			{
				//When need to add new Node
				head.children[index] = new Node(this.alphabets);
			}
			head = head.children[index];
		}
		if (head != null)
		{
			//indicates stop of string
			head.stop = true;
		}
	}
	//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;
				}
			}
		}
		if (text.length() > about.length())
		{
			return text;
		}
		else
		{
			return about;
		}
	}
	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
		Node head = root;
		for (int level = 0; level < length; level++)
		{
			//Get the index
			index = text[level] - 'a';
			if (head.children[index] == null)
			{
				//When need to add new Node
				head.children[index] = new Node(this.alphabets);
			}
			head = head.children[index];
		}
		if (head != null)
		{
			//indicates stop of string
			head.stop = true;
		}
	}
	//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;
				}
			}
		}
		if (text.Length > about.Length)
		{
			return text;
		}
		else
		{
			return about;
		}
	}
	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
    head = self.root
    level = 0
    while (level < length) :
      # Get the index
      index = ord(text[level]) - ord('a')
    
      if (head.children[index] == None) :
        # When need to add new Node
        head.children[index] = Node(self.alphabets)
      
      head = head.children[index]
      level += 1
    
    if (head != None) :
      # indicates stop of string
      head.stop = True
    
  
  # This function are finding largest word length string in given tire tree
  def longest_word(self, root, about) :
    text = about
    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
      
    
    if (len(text) > len(about)) :
      return text
    else :
      return about
    
  

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_reader :stop, :children
	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_reader :alphabets, :root
	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
		head = @root
		level = 0
		while (level < length)
		
			# Get the index
			index = (text[level]).ord - ('a').ord
			if (head.children[index] == nil)
			
				# When need to add new Node
				head.children[index] = Node.new(self.alphabets)
			end
			head = head.children[index]
			level += 1
		end
		if (head != nil)
		
			# indicates stop of string
			head.stop = true
		end
	end
	# This function are finding largest word length string in given tire tree
	def longest_word(root, about)
	
		text = about
		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
		if (text.length() > about.length())
		
			return text
		else
		
			return about
		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 head: Node = root;
		var level: Int = 0;
		while (level < length)
		{
			//Get the index
			index = text(level) - 'a';
			if (head.children(index) == null)
			{
				//When need to add new Node
				head.children(index) = new Node(this.alphabets);
			}
			head = head.children(index);
			level += 1;
		}
		if (head != null)
		{
			//indicates stop of string
			head.stop = true;
		}
	}
	//This function are finding largest word length string in given tire tree
	def longest_word(root: Node, about: String): String = {
		var text: String = about;
		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;
			}
		}
		if (text.length() > about.length())
		{
			return text;
		}
		else
		{
			return about;
		}
	}
}
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 head: Node? = self.root;
		var level: Int = 0;
		while (level < length)
		{
			//Get the index
			index = Int(UnicodeScalar(String(text[level]))!.value - 
                        UnicodeScalar("a")!.value);
			if (head!.children[index] == nil)
			{
				//When need to add new Node
				head!.children[index] = Node(self.alphabets);
			}
			head = head!.children[index];
			level += 1;
		}
		if (head != nil)
		{
			//indicates stop of string
			head!.stop = true;
		}
	}
	//This function are finding largest word length string in given tire tree
	func longest_word(_ root: Node? , _ about : String) -> String
	{
		var text: String = about;
		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;
			}
		}
		if (text.count > about.count)
		{
			return text;
		}
		else
		{
			return about;
		}
	}
}
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
    $head = $this->root;
    for ($level = 0; $level < $length; $level++)
    {
      //Get the index
      $index = ord($text[$level]) - ord('a');
      if ($head->children[$index] == null)
      {
        //When need to add new Node
        $head->children[$index] = new Node($this->alphabets);
      }
      $head = $head->children[$index];
    }
    if ($head != null)
    {
      //indicates stop of string
      $head->stop = true;
    }
  }
  //This function are finding largest word length string in given tire tree
  public  function longest_word($root, $about)
  {
    $text = $about;
    $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;
        }
      }
    }
    if (strlen($text) > strlen($about))
    {
      return $text;
    }
    else
    {
      return $about;
    }
  }
}

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
		var head = this.root;
		for (var level = 0; level < length; level++)
		{
			//Get the index
			index = text.charCodeAt(level) - 'a'.charCodeAt(0);
			if (head.children[index] == null)
			{
				//When need to add new Node
				head.children[index] = new Node(this.alphabets);
			}
			head = head.children[index];
		}
		if (head != null)
		{
			//indicates stop of string
			head.stop = true;
		}
	}
	//This function are finding largest word length string in given tire tree
	longest_word(root, about)
	{
		var text = about;
		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;
				}
			}
		}
		if (text.length > about.length)
		{
			return text;
		}
		else
		{
			return about;
		}
	}
}

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.

New Comment