Skip to main content

Trie insertion

The problem at hand revolves around the concept of Trie data structure and its insertion operation. A Trie, also known as a prefix tree, is a tree-like data structure used for efficient storage and retrieval of strings. It allows for quick lookups, insertions, and deletions of strings. The primary application of a Trie is in situations where we need to store and search for a large collection of strings efficiently, such as autocomplete in search engines or spell checkers.

In the given code, we are presented with a Java implementation of Trie insertion. The code aims to construct a Trie by inserting a set of words and then display the words in lexicographical order.

Problem Description

The problem can be summarized as follows:

  1. Create a Trie data structure with insert and display functionalities.
  2. Insert a set of words into the Trie.
  3. Display the inserted words in lexicographical order.

Example

Let's go through the example provided in the code to understand how it works.

Suppose we have the following words to insert: "cooky", "cool", "code", "comedy", "doc", and "deep".

Trie Tree example

Idea to Solve

To solve this problem, we need to create a Trie data structure that consists of nodes. Each node has an array of children, which is typically of size 26 to accommodate all lowercase English letters. The end attribute in each node indicates whether a word ends at that node.

The insertion process involves traversing through each character of the word and checking whether a node representing that character already exists. If not, we create a new node and continue. After processing all characters of the word, we mark the last node as the end of a word.

The display process involves recursively traversing the Trie and printing words whenever we encounter a node where end is true.

Pseudocode

Here's the pseudocode for the Trie insertion and display operations:

Class Node:
    boolean end
    Node[] children

    Constructor(size):
        Initialize children array of given size
        Set end to false

Class Trie:
    Node root

    Constructor:
        Initialize root node

    Insert(text):
        Initialize index = 0
        Initialize head node as root
        For each character c in text:
            Calculate index = c - 'a'
            If head.children[index] is null:
                head.children[index] = new Node(26)
            Move head to head.children[index]
        Set head.end = true

    Display(root, about):
        If root is not null:
            If root.end is true:
                Print about
            For i = 0 to 25:
                If root.children[i] is not null:
                    Recursively call Display(root.children[i], about + char(i + 'a'))

Main:
    Initialize Trie tree
    Insert words into tree
    Display the Trie

Algorithm Explanation

  1. Create a Node class with end attribute and an array of children.
  2. Create a Trie class with root attribute.
  3. In the Trie class constructor, initialize the root node with an array of size 26.
  4. Implement the insert method in the Trie class:
    • Initialize index to 0 and head to the root node.
    • Iterate through each character in the input word:
      • Calculate the index using the character's ASCII value ('a' subtracted).
      • If head.children[index] is null, create a new node in that position.
      • Move head to head.children[index].
    • After iterating through all characters, mark head.end as true to indicate the end of the word.
  5. Implement the display method in the Trie class:
    • If root is not null:
      • If root.end is true, print the current word represented by about.
      • Iterate through each child node:
        • If the child node is not null, recursively call display with the child node and the updated about.
  6. In the main function:
    • Create a Trie instance called tree.
    • Insert the given words into the tree.
    • Display the Trie using the display method.

Code Solution

/*
 Java program
 Trie insert operation
*/
class Node
{
	// Indicates end of string
	public boolean end;
	public Node[] children;
	public Node(int size)
	{
		children = new Node[size];
		end = false;
	}
}
public class Trie
{
	public Node root;
	public Trie()
	{
		root = new Node(26);
	}
	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(26);
			}
			head = head.children[index];
		}
		if (head != null)
		{
			// Indicates end of string
			head.end = true;
		}
	}
	public void display(Node root, String about)
	{
		if (root != null)
		{
			if (root.end == true)
			{
				System.out.println(about);
			}
			for (int i = 0; i < 26; i++)
			{
				if (root.children[i] != null)
				{
					display(root.children[i], about + ((char)(i + 97)));
				}
			}
		}
	}
	public static void main(String[] args)
	{
		// Make new tree
		Trie tree = new Trie();
		tree.insert("cooky");
		tree.insert("cool");
		tree.insert("code");
		tree.insert("comedy");
		tree.insert("doc");
		tree.insert("deep");
		System.out.print("Trie Data \n");
		tree.display(tree.root, "");
	}
}

Output

Trie Data
code
comedy
cooky
cool
deep
doc
// Include header file
#include <iostream>
#include <string>
using namespace std;
/*
 C++ program
 Trie insert operation
*/
class Node
{
	public:
	// Indicates end of string
	bool end;
	Node **children;
	Node(int size)
	{
      	this->children = new Node*[size];
      	for (int i = 0; i < 26; ++i)
		{
			this->children[i] = NULL;
		}
		this->end = false;
	}
};
class Trie
{
	public: Node *root;
	Trie()
	{
		this->root = new Node(26);
	}
	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 = 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(26);
			}
			head = head->children[index];
		}
		if (head != NULL)
		{
			// Indicates end of string
			head->end = true;
		}
	}
	void display(Node *root, string about)
	{
		if (root != NULL)
		{
			if (root->end == true)
			{
				cout << about << endl;
			}
			for (int i = 0; i < 26; i++)
			{
				if (root->children[i] != NULL)
				{
					this->display(root->children[i], 
                                  about + ((char)(i + 97)));
				}
			}
		}
	}
};
int main()
{
	// Make new tree
	Trie *tree = new Trie();
	tree->insert("cooky");
	tree->insert("cool");
	tree->insert("code");
	tree->insert("comedy");
	tree->insert("doc");
	tree->insert("deep");
	cout << "Trie Data \n";
	tree->display(tree->root, "");
	return 0;
}

Output

Trie Data
code
comedy
cooky
cool
deep
doc
// Include namespace system
using System;
/*
 Csharp program
 Trie insert operation
*/
public class Node
{
	// Indicates end of string
	public Boolean end;
	public Node[] children;
	public Node(int size)
	{
		this.children = new Node[size];
		this.end = false;
	}
}
public class Trie
{
	public Node root;
	public Trie()
	{
		this.root = new Node(26);
	}
	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 = 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(26);
			}
			head = head.children[index];
		}
		if (head != null)
		{
			// Indicates end of string
			head.end = true;
		}
	}
	public void display(Node root, String about)
	{
		if (root != null)
		{
			if (root.end == true)
			{
				Console.WriteLine(about);
			}
			for (int i = 0; i < 26; i++)
			{
				if (root.children[i] != null)
				{
					this.display(root.children[i], 
                                 about + ((char)(i + 97)));
				}
			}
		}
	}
	public static void Main(String[] args)
	{
		// Make new tree
		Trie tree = new Trie();
		tree.insert("cooky");
		tree.insert("cool");
		tree.insert("code");
		tree.insert("comedy");
		tree.insert("doc");
		tree.insert("deep");
		Console.Write("Trie Data \n");
		tree.display(tree.root, "");
	}
}

Output

Trie Data
code
comedy
cooky
cool
deep
doc
package main
import "fmt"
/*
 Go program
 Trie insert operation
*/
type Node struct {
	// Indicates end of string
	end bool
	children []*Node
}
func getNode(size int) * Node {
	var me *Node = &Node {}
	me.children = make([] *Node, size)
	me.end = false
	return me
}
type Trie struct {
	root * Node
}
func getTrie() * Trie {
	var me *Trie = &Trie {}
	me.root = getNode(26)
	return me
}
func(this Trie) insert(text string) {
	// First get the length of text
	var length int = len(text)
	// This variable are used to task find the 
	// index location of character
	var index int = 0
	// Get the root node
	var head * Node = this.root
	for level := 0 ; level < length ; level++ {
		// Get the index
		index = int(text[level] - 'a')
		if head.children[index] == nil {
			// When need to add new Node
			head.children[index] = getNode(26)
		}
		head = head.children[index]
	}
	if head != nil {
		// Indicates end of string
		head.end = true
	}
}
func(this Trie) display(root * Node, about string) {
	if root != nil {
		if root.end == true {
			fmt.Println(about)
		}
		for i := 0 ; i < 26 ; i++ {
			if root.children[i] != nil {
				this.display(root.children[i], 
					about + string((byte((i + 97)))))
			}
		}
	}
}
func main() {
	// Make new tree
	var tree * Trie = getTrie()
	tree.insert("cooky")
	tree.insert("cool")
	tree.insert("code")
	tree.insert("comedy")
	tree.insert("doc")
	tree.insert("deep")
	fmt.Print("Trie Data \n")
	tree.display(tree.root, "")
}

Output

Trie Data
code
comedy
cooky
cool
deep
doc
<?php
/*
 Php program
 Trie insert operation
*/
class Node
{
	// Indicates end of string
	public $end;
	public $children;
	public	function __construct($size)
	{
		$this->children = array_fill(0, $size, NULL);
		$this->end = false;
	}
}
class Trie
{
	public $root;
	public	function __construct()
	{
		$this->root = new Node(26);
	}
	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(26);
			}
			$head = $head->children[$index];
		}
		if ($head != NULL)
		{
			// Indicates end of string
			$head->end = true;
		}
	}
	public	function display($root, $about)
	{
		if ($root != NULL)
		{
			if ($root->end == true)
			{
				echo($about.
					"\n");
			}
			for ($i = 0; $i < 26; $i++)
			{
				if ($root->children[$i] != NULL)
				{
					$this->display($root->children[$i], 
                                   $about.strval((chr(($i + 97)))));
				}
			}
		}
	}
}

function main()
{
	// Make new tree
	$tree = new Trie();
	$tree->insert("cooky");
	$tree->insert("cool");
	$tree->insert("code");
	$tree->insert("comedy");
	$tree->insert("doc");
	$tree->insert("deep");
	echo("Trie Data \n");
	$tree->display($tree->root, "");
}
main();

Output

Trie Data
code
comedy
cooky
cool
deep
doc
/*
 Node JS program
 Trie insert operation
*/
class Node
{
	constructor(size)
	{
		this.children = Array(size).fill(null);
		this.end = false;
	}
}
class Trie
{
	constructor()
	{
		this.root = new Node(26);
	}
	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.charAt(level).charCodeAt(0) - 'a'.charCodeAt(0);
			if (head.children[index] == null)
			{
				// When need to add new Node
				head.children[index] = new Node(26);
			}
			head = head.children[index];
		}
		if (head != null)
		{
			// Indicates end of string
			head.end = true;
		}
	}
	display(root, about)
	{
		if (root != null)
		{
			if (root.end == true)
			{
				console.log(about);
			}
			for (var i = 0; i < 26; i++)
			{
				if (root.children[i] != null)
				{
					this.display(root.children[i],
                    about + (String.fromCharCode((i + 97))));
				}
			}
		}
	}
}

function main()
{
	// Make new tree
	var tree = new Trie();
	tree.insert("cooky");
	tree.insert("cool");
	tree.insert("code");
	tree.insert("comedy");
	tree.insert("doc");
	tree.insert("deep");
	process.stdout.write("Trie Data \n");
	tree.display(tree.root, "");
}
main();

Output

Trie Data
code
comedy
cooky
cool
deep
doc
# Python 3 program
# Trie insert operation
class Node :
	#  Indicates end of string
	def __init__(self, size) :
		self.children = [None] * (size)
		self.end = False
	

class Trie :
	def __init__(self) :
		self.root = Node(26)
	
	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(26)
			
			head = head.children[index]
			level += 1
		
		if (head != None) :
			#  Indicates end of string
			head.end = True
		
	
	def display(self, root, about) :
		if (root != None) :
			if (root.end == True) :
				print(about)
			
			i = 0
			while (i < 26) :
				if (root.children[i] != None) :
					self.display(root.children[i], 
                                 about + str((chr((i + 97)))))
				
				i += 1
			
		
	

def main() :
	#  Make new tree
	tree = Trie()
	tree.insert("cooky")
	tree.insert("cool")
	tree.insert("code")
	tree.insert("comedy")
	tree.insert("doc")
	tree.insert("deep")
	print("Trie Data ")
	tree.display(tree.root, "")

if __name__ == "__main__": main()

Output

Trie Data
code
comedy
cooky
cool
deep
doc
# Ruby program
# Trie insert operation
class Node 
	# Define the accessor and reader of class Node
	attr_reader :end, :children
	attr_accessor :end, :children
	#  Indicates end of string
	def initialize(size) 
		self.children = Array.new(size) {nil}
		self.end = false
	end

end

class Trie 
	# Define the accessor and reader of class Trie
	attr_reader :root
	attr_accessor :root
	def initialize() 
		self.root = Node.new(26)
	end

	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 = self.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(26)
			end

			head = head.children[index]
			level += 1
		end

		if (head != nil) 
			#  Indicates end of string
			head.end = true
		end

	end

	def display(root, about) 
		if (root != nil) 
			if (root.end == true) 
				print(about, "\n")
			end

			i = 0
			while (i < 26) 
				if (root.children[i] != nil) 
					self.display(root.children[i], 
                                 about +(((i + 97)).chr).to_s)
				end

				i += 1
			end

		end

	end

end

def main() 
	#  Make new tree
	tree = Trie.new()
	tree.insert("cooky")
	tree.insert("cool")
	tree.insert("code")
	tree.insert("comedy")
	tree.insert("doc")
	tree.insert("deep")
	print("Trie Data \n")
	tree.display(tree.root, "")
end

main()

Output

Trie Data 
code
comedy
cooky
cool
deep
doc

import scala.collection.mutable._;
/*
 Scala program
 Trie insert operation
*/
class Node(
	// Indicates end of string
	var end: Boolean,
		var children: Array[Node])
{
	def this(size: Int)
	{
		this(false, Array.fill[Node](size)(null))
	}
}
class Trie(var root: Node)
{
	def this()
	{
		this(new Node(26))
	}
	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.charAt(level).toInt - 'a'.toInt;
			if (head.children(index) == null)
			{
				// When need to add new Node
				head.children(index) = new Node(26);
			}
			head = head.children(index);
			level += 1;
		}
		if (head != null)
		{
			// Indicates end of string
			head.end = true;
		}
	}
	def display(root: Node, about: String): Unit = {
		if (root != null)
		{
			if (root.end == true)
			{
				println(about);
			}
			var i: Int = 0;
			while (i < 26)
			{
				if (root.children(i) != null)
				{
					display(root.children(i), 
                    about + ((i + 97).toChar).toString());
				}
				i += 1;
			}
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		// Make new tree
		var tree: Trie = new Trie();
		tree.insert("cooky");
		tree.insert("cool");
		tree.insert("code");
		tree.insert("comedy");
		tree.insert("doc");
		tree.insert("deep");
		print("Trie Data \n");
		tree.display(tree.root, "");
	}
}

Output

Trie Data
code
comedy
cooky
cool
deep
doc
import Foundation;
/*
 Swift 4 program
 Trie insert operation
*/
class Node
{
	// Indicates end of string
	var end: Bool;
	var children: [Node?];
	init(_ size: Int)
	{
		self.children = Array(repeating: nil, count: size);
		self.end = false;
	}
}
class Trie
{
	var root: Node? ;
	init()
	{
		self.root = Node(26);
	}
	func insert(_ data: String)
	{
      	let text = Array(data);
		// First get the length of text
		let length: Int = text.count;
		// 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) -
              Int(UnicodeScalar(String("a"))!.value);
			if (head!.children[index] == nil)
			{
				// When need to add new Node
				head!.children[index] = Node(26);
			}
			head = head!.children[index];
			level += 1;
		}
		if (head  != nil)
		{
			// Indicates end of string
			head!.end = true;
		}
	}
	func display(_ root: Node? , _ about : String)
	{
		if (root  != nil)
		{
			if (root!.end == true)
			{
				print(about);
			}
			var i: Int = 0;
			while (i < 26)
			{
				if (root!.children[i]  != nil)
				{
					self.display(root!.children[i], 
                      about + String(UnicodeScalar(UInt8(i + 97))));
				}
				i += 1;
			}
		}
	}
}
func main()
{
	// Make new tree
	let tree: Trie = Trie();
	tree.insert("cooky");
	tree.insert("cool");
	tree.insert("code");
	tree.insert("comedy");
	tree.insert("doc");
	tree.insert("deep");
	print("Trie Data ");
	tree.display(tree.root, "");
}
main();

Output

Trie Data
code
comedy
cooky
cool
deep
doc
/*
 Kotlin program
 Trie insert operation
*/
class Node
{
	// Indicates end of string
	var end: Boolean;
	var children: Array <Node?> ;
	constructor(size: Int)
	{
		this.children = Array(size)
		{
			null
		};
		this.end = false;
	}
}
class Trie
{
	var root: Node ? ;
	constructor()
	{
		this.root = Node(26);
	}
	fun insert(text: String): Unit
	{
		// First get the length of text
		val length: Int = text.length;
		// This variable are used to task find the 
		// index location of character
		var index: Int ;
		// Get the root node
		var head: Node ? = this.root;
		var level: Int = 0;
		while (level < length)
		{
			// Get the index
			index = text.get(level).toInt() - 'a'.toInt();
			if (head!!.children[index] == null)
			{
				// When need to add new Node
				head.children[index] = Node(26);
			}
			head = head.children[index];
			level += 1;
		}
		if (head != null)
		{
			// Indicates end of string
			head.end = true;
		}
	}
	fun display(root: Node ? , about : String): Unit
	{
		if (root != null)
		{
			if (root.end == true)
			{
				println(about);
			}
			var i: Int = 0;
			while (i < 26)
			{
				if (root.children[i] != null)
				{
					this.display(root.children[i], 
                                 about + ((i + 97).toChar()).toString());
				}
				i += 1;
			}
		}
	}
}
fun main(args: Array < String > ): Unit
{
	// Make new tree
	val tree: Trie = Trie();
	tree.insert("cooky");
	tree.insert("cool");
	tree.insert("code");
	tree.insert("comedy");
	tree.insert("doc");
	tree.insert("deep");
	print("Trie Data \n");
	tree.display(tree.root, "");
}

Output

Trie Data
code
comedy
cooky
cool
deep
doc

Time Complexity

The time complexity of the Trie insertion operation is determined by the length of the longest word among the inserted words, denoted as m, and the total number of inserted words, denoted as n. In the worst case, where there are no common prefixes among the words, the insertion process requires traversing m levels of the Trie for each of the n words. Therefore, the time complexity is O(m * n).

For the display operation, the time complexity depends on the number of nodes in the Trie, which is proportional to the total number of characters in all inserted words. Hence, the time complexity for displaying the Trie is O(total characters in Trie).

Last updated on by Kalkicode




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





♲ Kalkicode     ⟶ 434 Day ago 
You are right [-std=c++20] , we are updating our code as soon as possible.
♲ Maurice     ⟶ 458 Day ago 
This is filled with memory leaks... https://godbolt.org/z/Ts6TnsEoM