Skip to main content

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"
Trie Tree example

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
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