Posted on by Kalkicode
Code Tree

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

## 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
For each character c in text:
Calculate index = c - 'a'

If root is not null:
If root.end is true:
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
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 void display(Node root, String about)
{
if (root != null)
{
if (root.end == true)
{
}
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
for (int level = 0; level < length; level++)
{
// Get the index
index = text[level] - 'a';
{
// When need to add new Node
}
}
{
// Indicates end of string
}
}
{
if (root != NULL)
{
if (root->end == true)
{
}
for (int i = 0; i < 26; i++)
{
if (root->children[i] != NULL)
{
this->display(root->children[i],
}
}
}
}
};
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
for (int level = 0; level < length; level++)
{
// Get the index
index = text[level] - 'a';
{
// When need to add new Node
}
}
{
// Indicates end of string
}
}
public void display(Node root, String about)
{
if (root != null)
{
if (root.end == true)
{
}
for (int i = 0; i < 26; i++)
{
if (root.children[i] != null)
{
this.display(root.children[i],
}
}
}
}
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')
// When need to add new Node
}
}
// Indicates end of string
}
}
func(this Trie) display(root * Node, about string) {
if root != nil {
if root.end == true {
}
for i := 0 ; i < 26 ; i++ {
if root.children[i] != nil {
this.display(root.children[i],
}
}
}
}
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
for (\$level = 0; \$level < \$length; \$level++)
{
// Get the index
\$index = ord(\$text[\$level]) - ord('a');
{
// When need to add new Node
}
}
{
// Indicates end of string
}
}
{
if (\$root != NULL)
{
if (\$root->end == true)
{
"\n");
}
for (\$i = 0; \$i < 26; \$i++)
{
if (\$root->children[\$i] != NULL)
{
\$this->display(\$root->children[\$i],
}
}
}
}
}

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
for (var level = 0; level < length; level++)
{
// Get the index
index = text.charAt(level).charCodeAt(0) - 'a'.charCodeAt(0);
{
// When need to add new Node
}
}
{
// Indicates end of string
}
}
{
if (root != null)
{
if (root.end == true)
{
}
for (var i = 0; i < 26; i++)
{
if (root.children[i] != null)
{
this.display(root.children[i],
}
}
}
}
}

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
level = 0
while (level < length) :
#  Get the index
index = ord(text[level]) - ord('a')
#  When need to add new Node

level += 1

#  Indicates end of string

if (root != None) :
if (root.end == True) :

i = 0
while (i < 26) :
if (root.children[i] != None) :
self.display(root.children[i],

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_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_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
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 end of string
end

end

if (root != nil)
if (root.end == true)
end

i = 0
while (i < 26)
if (root.children[i] != nil)
self.display(root.children[i],
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 level: Int = 0;
while (level < length)
{
// Get the index
index = text.charAt(level).toInt - 'a'.toInt;
{
// When need to add new Node
}
level += 1;
}
{
// Indicates end of string
}
}
def display(root: Node, about: String): Unit = {
if (root != null)
{
if (root.end == true)
{
}
var i: Int = 0;
while (i < 26)
{
if (root.children(i) != null)
{
display(root.children(i),
}
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 level: Int = 0;
while (level < length)
{
// Get the index
index = Int(UnicodeScalar(String(text[level]))!.value) -
Int(UnicodeScalar(String("a"))!.value);
{
// When need to add new Node
}
level += 1;
}
{
// Indicates end of string
}
}
func display(_ root: Node? , _ about : String)
{
if (root  != nil)
{
if (root!.end == true)
{
}
var i: Int = 0;
while (i < 26)
{
if (root!.children[i]  != nil)
{
self.display(root!.children[i],
}
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();
{
// When need to add new Node
}
level += 1;
}
{
// Indicates end of string
}
}
fun display(root: Node ? , about : String): Unit
{
if (root != null)
{
if (root.end == true)
{
}
var i: Int = 0;
while (i < 26)
{
if (root.children[i] != null)
{
this.display(root.children[i],
}
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).

## 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     634 Day ago
``You are right [-std=c++20] , we are updating our code as soon as possible. ``
Maurice     658 Day ago
``This is filled with memory leaks... https://godbolt.org/z/Ts6TnsEoM``
Categories
Relative Post