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:
- Create a Trie data structure with insert and display functionalities.
- Insert a set of words into the Trie.
- 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".

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
- Create a
Node
class withend
attribute and an array ofchildren
. - Create a
Trie
class withroot
attribute. - In the
Trie
class constructor, initialize the root node with an array of size 26. - Implement the
insert
method in theTrie
class:- Initialize
index
to 0 andhead
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
tohead.children[index]
.
- After iterating through all characters, mark
head.end
as true to indicate the end of the word.
- Initialize
- Implement the
display
method in theTrie
class:- If
root
is not null:- If
root.end
is true, print the current word represented byabout
. - Iterate through each child node:
- If the child node is not null, recursively call
display
with the child node and the updatedabout
.
- If the child node is not null, recursively call
- If
- If
- In the
main
function:- Create a
Trie
instance calledtree
. - Insert the given words into the
tree
. - Display the Trie using the
display
method.
- Create a
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).
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