Trie insertion
Trie is an very useful data structure. which can be use to search, delete ,add in particular string linear time. Each node of trie tree consist two fields. First is an a array of objects (structure) that is size of 26. and second is an variable which are used as flag to indicate end of string. Let's see an example to insert the following text data into empty trie tree.
"cooky"
"cool"
"code"
"comedy"
"doc"
"deep"

Each node of tree tree is capable to contains 26 childnodes. And each node provides an alphabet information. We can design trie tree using [a-z] or [A-Z] alphabet its depending upon situations. You can also use 255 size to target all alphabets and special characters. Here given an example of 26 size which is based on small letters [a-z].
Here given code implementation process.
/*
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
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