Trie Deletion
In computer science, a trie is a tree-like data structure often used for efficient string manipulation tasks. In this case, we'll explore how to implement the deletion operation for a trie data structure. Trie deletion involves removing a string from the trie while ensuring that the trie's structure and other strings remain intact.
Problem Statement
Given a Trie data structure with strings inserted into it, the task is to implement the deletion operation for a specific string. The deletion operation should handle scenarios where the deleted string is a prefix of other strings or is part of other strings.
Example
Consider a Trie with the strings "cooky" and "cool" inserted into it. We'll perform the deletion of the string "cooky" and observe the changes in the trie.

Idea to Solve
To solve this problem, we need to carefully navigate the trie to locate the nodes corresponding to the characters of the string to be deleted. Once we find the last node representing the end of the string, we can mark it as not being the end of a string (if it's part of other strings) or remove it completely (if it's not part of any other string).
Pseudocode
lastNode(text):
node = root
for each character in text:
index = character - 'a'
if node.children[index] is null:
return null
node = node.children[index]
if node is not null and node.end is true:
return node
else:
return null
deleteNode(text, root, level):
if root is not null:
if level is equal to length of text:
if emptyNode(root):
return null
return root
index = text.charAt(level) - 'a'
root.children[index] = deleteNode(text, root.children[index], level + 1)
if root.end is false and emptyNode(root):
return null
return root
delete(text):
last = lastNode(text)
if last is not null:
if emptyNode(last):
deleteNode(text, root, 0)
else:
last.end = false
print "Delete Text " + text
else:
print "Not Exist Delete Text String : " + text
Algorithm Explanation
-
lastNode(text)
: Traverse the trie based on characters in thetext
. If the traversal reaches the last character of thetext
, return the corresponding node if it marks the end of a string, otherwise returnnull
. -
deleteNode(text, root, level)
: Recursively traverse the trie to find the node corresponding to the last character oftext
. If found, and iflevel
is the length oftext
, check if the node is a leaf node. If it's a leaf node and has no children, returnnull
to indicate that this node should be removed. If it's not a leaf node, or if it's not the end of a string, retain the node. Finally, ifroot.end
is false and the node is empty, returnnull
. -
delete(text)
: Get the last node of thetext
from the trie. If the last node exists, check if it's a leaf node. If it's a leaf node, delete it using thedeleteNode
function. If it's not a leaf node, simply mark it as not being the end of a string. Print relevant messages accordingly.
Code Solution
/*
C++ program
Trie Deletion
*/
#include <iostream>
#include <string.h>
#define ALPHABETS 26
using namespace std;
class Node {
public:
bool end;
Node *children[ALPHABETS];
Node() {
this->end = false;
for (int i = 0; i < ALPHABETS; ++i) {
this->children[i] = NULL;
}
}
};
class Trie {
public:
Node *root;
Trie() {
this->root = new Node();
}
//Search given text is exist in tire
bool search(string text) {
int length = text.size();
int index = 0;
Node *head = this->root;
for (int level = 0; level < length; level++) {
index = text[level] - 'a';
if (head->children[index] == NULL) {
return false;
}
head = head->children[index];
}
if (head != NULL && head->end == true) {
return true;
} else {
return false;
}
}
void insert(string text) {
int length = text.size();
int index = 0;
Node *head = this->root;
for (int level = 0; level < length; level++) {
index = text[level] - 'a';
if (head->children[index] == NULL) {
head->children[index] = new Node();
}
head = head->children[index];
}
if (head != NULL) {
//indicates end of string
head->end = true;
}
}
bool emptyNode(Node *root) {
for (int i = 0; i < ALPHABETS; i++) {
if (root->children[i] != NULL) {
return false;
}
}
return true;
}
Node *lastNode(string text) {
int length = text.size();
int index = 0;
Node *head = this->root;
for (int level = 0; level < length; level++) {
index = text[level] - 'a';
if (head->children[index] == NULL) {
return NULL;
}
head = head->children[index];
}
if (head != NULL && head->end == true) {
return head;
} else {
return NULL;
}
}
//This method are handle the request of deleted text in trie tree
Node *deleteNode(string text, Node *root, int level) {
if (root != NULL) {
if (level == text.size()) {
if (this->emptyNode(root)) {
return NULL;
}
return root;
}
int index = text[level] - 'a';
root->children[index] = this->deleteNode(text, root->children[index], level + 1);
if (root->end == false && this->emptyNode(root)) {
return NULL;
}
}
return root;
}
void deleteText(string text) {
Node *last = this->lastNode(text);
if (last != NULL) {
if (this->emptyNode(last)) {
this->deleteNode(text, this->root, 0);
} else {
last->end = false;
}
cout << "Delete Text " << text << endl;
} else {
cout << "Not Exist Delete Text String : " << text << endl;
}
}
};
int main() {
Trie obj;
obj.insert("cooky");
obj.insert("cool");
string text = "cooky";
if (obj.search(text)) {
cout << "Exist : " << text << endl;
} else {
cout << "Not Exist : " << text << endl;
}
obj.deleteText("cooky");
if (obj.search(text)) {
cout << "Exist : " << text << endl;
} else {
cout << "Not Exist : " << text << endl;
}
return 0;
}
Output
Exist : cooky
Delete Text cooky
Not Exist : cooky
/*
Java program
Trie Deletion
*/
class Node {
//Indicates end of string
public boolean end;
public Node[] children;
public Node(int size) {
end = false;
children = new Node[size];
}
}
public class Trie {
public int ALPHABETS = 26;
public Node root;
public Trie() {
root = new Node(ALPHABETS);
}
//Search given text is exist in tire
public boolean search(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) {
return false;
}
head = head.children[index];
}
if (head != null && head.end == true) {
return true;
} else {
return false;
}
}
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(ALPHABETS);
}
head = head.children[index];
}
if (head != null) {
//indicates end of string
head.end = true;
}
}
public boolean emptyNode(Node root) {
for (int i = 0; i < ALPHABETS; i++) {
if (root.children[i] != null) {
return false;
}
}
return true;
}
//Search given text is exist in tire
public Node lastNode(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) {
return null;
}
head = head.children[index];
}
if (head != null && head.end == true) {
return head;
} else {
return null;
}
}
public Node deleteNode(String text, Node root, int level) {
if (root != null) {
//if get last node of string
if (level == text.length()) {
if (emptyNode(root)) {
return null;
}
return root;
}
int index = text.charAt(level) - 'a';
root.children[index] =
deleteNode(text, root.children[index], level + 1);
if (root.end == false && emptyNode(root)) {
return null;
}
}
return root;
}
//This method are handle the request of deleted text in trie tree
public void delete(String text) {
//Get last node of deleted text
Node last = lastNode(text);
if (last != null) {
if (emptyNode(last)) {
//If last node of deleted text is not a part of other text string
deleteNode(text, root, 0);
} else {
last.end = false;
}
System.out.println("Delete Text " + text);
} else {
//When node element are not exist
System.out.println("Not Exist Delete Text String : " + text);
}
}
public static void main(String[] args) {
//Make object
Trie obj = new Trie();
obj.insert("cooky");
obj.insert("cool");
String text = "cooky";
if (obj.search(text)) {
System.out.println("Exist : " + text);
} else {
System.out.println("Not Exist : " + text);
}
obj.delete("cooky");
//After Delete
if (obj.search(text)) {
System.out.println("Exist : " + text);
} else {
System.out.println("Not Exist : " + text);
}
}
}
Output
Exist : cooky
Delete Text cooky
Not Exist : cooky
#Python Code
#Trie Deletion
class Node :
def __init__(self,size) :
self.end = False
self.children = [None] * size
class Trie :
def __init__(self) :
self.ALPHABETS = 26
self.root = Node(self.ALPHABETS)
def search(self,text) :
length = len(text)
index = 0
head = self.root
level = 0
while ( level < length ) :
index = ord(text[level]) - ord('a')
if (head.children[index] == None) :
return False
head = head.children[index]
level += 1
if (head != None and head.end == True) :
return True
else :
return False
def insert(self,text) :
length = len(text)
index = 0
head = self.root
level = 0
while ( level < length ) :
index = ord(text[level]) - ord('a')
if (head.children[index] == None) :
head.children[index] = Node(self.ALPHABETS)
head = head.children[index]
level += 1
if (head != None) :
head.end = True
def emptyNode(self,root) :
i = 0
while ( i < self.ALPHABETS ) :
if (self.root.children[i] != None) :
return False
i += 1
return True
def lastNode(self,text) :
length = len(text)
index = 0
head = self.root
level = 0
while ( level < length ) :
index = ord(text[level]) - ord('a')
if (head.children[index] == None) :
return None
head = head.children[index]
level += 1
if (head != None and head.end == True) :
return head
else :
return None
def deleteNode(self,text, root, level) :
if (self.root != None) :
if (level == len(text)) :
if (self.emptyNode(self.root)) :
return None
return self.root
index = ord(text[level]) - ord('a')
self.root.children[index] = self.deleteNode(text, self.root.children[index], level + 1)
if (self.root.end == False and self.emptyNode(self.root)) :
return None
return self.root
def delete(self,text) :
last = self.lastNode(text)
if (last != None) :
if (self.emptyNode(last)) :
self.deleteNode(text, self.root, 0)
else :
last.end = False
print("Delete Text ", text)
else :
print("Not Exist Delete Text String : ", text)
def main() :
obj = Trie()
obj.insert("cooky")
obj.insert("cool")
text = "cooky"
if (obj.search(text)) :
print("Exist : ", text)
else :
print("Not Exist : ", text)
obj.delete("cooky")
if (obj.search(text)) :
print("Exist : ", text)
else :
print("Not Exist : ", text)
if __name__ == "__main__":
main()
Output
Exist : cooky
Delete Text cooky
Not Exist : cooky
/*
C# program
Trie Deletion
*/
using System;
public class Node {
//Indicates end of string
public Boolean end;
public Node[] children;
public Node(int size) {
end = false;
children = new Node[size];
}
}
public class Trie {
public int ALPHABETS = 26;
public Node root;
public Trie() {
root = new Node(ALPHABETS);
}
//Search given text is exist in tire
public Boolean search(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[level] - 'a';
if (head.children[index] == null) {
return false;
}
head = head.children[index];
}
if (head != null && head.end == true) {
return true;
} else {
return false;
}
}
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[level] - 'a';
if (head.children[index] == null) {
//When need to add new Node
head.children[index] = new Node(ALPHABETS);
}
head = head.children[index];
}
if (head != null) {
//indicates end of string
head.end = true;
}
}
public Boolean emptyNode(Node root) {
for (int i = 0; i < ALPHABETS; i++) {
if (root.children[i] != null) {
return false;
}
}
return true;
}
//Search given text is exist in tire
public Node lastNode(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[level] - 'a';
if (head.children[index] == null) {
return null;
}
head = head.children[index];
}
if (head != null && head.end == true) {
return head;
} else {
return null;
}
}
public Node deleteNode(String text, Node root, int level) {
if (root != null) {
//if get last node of string
if (level == text.Length) {
if (emptyNode(root)) {
return null;
}
return root;
}
int index = text[level] - 'a';
root.children[index] =
deleteNode(text, root.children[index], level + 1);
if (root.end == false && emptyNode(root)) {
return null;
}
}
return root;
}
//This method are handle the request of deleted text in trie tree
public void delete(String text) {
//Get last node of deleted text
Node last = lastNode(text);
if (last != null) {
if (emptyNode(last)) {
//If last node of deleted text is not a part of other text string
deleteNode(text, root, 0);
} else {
last.end = false;
}
Console.WriteLine("Delete Text " + text);
} else {
//When node element are not exist
Console.WriteLine("Not Exist Delete Text String : " + text);
}
}
public static void Main(String[] args) {
//Make object
Trie obj = new Trie();
obj.insert("cooky");
obj.insert("cool");
String text = "cooky";
if (obj.search(text)) {
Console.WriteLine("Exist : " + text);
} else {
Console.WriteLine("Not Exist : " + text);
}
obj.delete("cooky");
//After Delete
if (obj.search(text)) {
Console.WriteLine("Exist : " + text);
} else {
Console.WriteLine("Not Exist : " + text);
}
}
}
Output
Exist : cooky
Delete Text cooky
Not Exist : cooky
<?php
/*
Php program
Trie Deletion
*/
class Node {
public $end;
public $children;
function __construct($size) {
$this->end = false;
$this->children = array_fill(0, $size, NULL);
}
}
class Trie {
public $ALPHABETS = 26;
public $root;
function __construct() {
$this->root = new Node($this->ALPHABETS);
}
public function search($text) {
$length = strlen($text);
$index = 0;
$head = $this->root;
for ($level = 0; $level < $length; $level++) {
$index = ord($text[$level]) - ord('a');
if ($head->children[$index] == null) {
return false;
}
$head = $head->children[$index];
}
if ($head != null && $head->end == true) {
return true;
} else {
return false;
}
}
public function insert($text) {
$length = strlen($text);
$index = 0;
$head = $this->root;
for ($level = 0; $level < $length; $level++) {
$index = ord($text[$level]) - ord('a');
if ($head->children[$index] == null) {
$head->children[$index] = new Node($this->ALPHABETS);
}
$head = $head->children[$index];
}
if ($head != null) {
$head->end = true;
}
}
public function emptyNode($root) {
for ($i = 0; $i < $this->ALPHABETS; $i++) {
if ($this->root->children[$i] != null) {
return false;
}
}
return true;
}
public function lastNode($text) {
$length = strlen($text);
$index = 0;
$head = $this->root;
for ($level = 0; $level < $length; $level++) {
$index = ord($text[$level]) - ord('a');
if ($head->children[$index] == null) {
return null;
}
$head = $head->children[$index];
}
if ($head != null && $head->end == true) {
return $head;
} else {
return null;
}
}
public function deleteNode($text, $root, $level) {
if ($this->root != null) {
if ($level == strlen($text)) {
if ($this->emptyNode($this->root)) {
return null;
}
return $this->root;
}
$index = ord($text[$level]) - ord('a');
$this->root->children[$index] = $this->deleteNode($text, $this->root->children[$index], $level + 1);
if ($this->root->end == false && $this->emptyNode($this->root)) {
return null;
}
}
return $this->root;
}
public function delete($text) {
$last = $this->lastNode($text);
if ($last != null) {
if ($this->emptyNode($last)) {
$this->deleteNode($text, $this->root, 0);
} else {
$last->end = false;
}
echo("Delete Text $text\n");
} else {
echo("Not Exist Delete Text String : $text\n");
}
}
}
function main() {
$obj = new Trie();
$obj->insert("cooky");
$obj->insert("cool");
$text = "cooky";
if ($obj->search($text)) {
echo ("Exist : $text\n");
} else {
echo("Not Exist : $text \n");
}
$obj->delete("cooky");
if ($obj->search($text)) {
echo("Exist : $text\n");
} else {
echo("Not Exist : $text\n");
}
}
main();
Output
Exist : cooky
Delete Text cooky
Not Exist : cooky
#
# Ruby program
# Trie Deletion
#
class Node
attr_reader :end, :children
attr_accessor :end, :children
def initialize(size)
@end = false
@children = Array.new(size){nil}
end
end
class Trie
attr_reader :ALPHABETS, :root
attr_accessor :ALPHABETS, :root
def initialize()
@ALPHABETS = 26
@root = Node.new(@ALPHABETS)
end
def search(text)
length = text.length
location = 0
head = @root
level = 0
while ( level < length ) do
location = text[level].ord-'a'.ord
if (head.children[location] == nil)
return false
end
head = head.children[location]
level += 1
end
if (head != nil and head.end == true)
return true
else
return false
end
end
def insert(text)
length = text.length
location = 0
head = @root
level = 0
while ( level < length )
location = text[level].ord-'a'.ord
if (head.children[location] == nil)
head.children[location] = Node.new(@ALPHABETS)
end
head = head.children[location]
level += 1
end
if (head != nil)
head.end = true
end
end
def emptyNode(root)
i = 0
while ( i < @ALPHABETS )
if (@root.children[i] != nil)
return false
end
i += 1
end
return true
end
def lastNode(text)
length = text.length
location = 0
head = @root
level = 0
while ( level < length )
location = text[level].ord-'a'.ord
if (head.children[location] == nil)
return nil
end
head = head.children[location]
level += 1
end
if (head != nil and head.end == true)
return head
else
return nil
end
end
def deleteNode(text, root, level)
if (@root != nil)
if (level == text.length)
if (self.emptyNode(@root))
return nil
end
return @root
end
location = text[level].ord-'a'.ord
@root.children[location] = self.deleteNode(text, @root.children[location], level + 1)
if (@root.end == false and self.emptyNode(@root))
return nil
end
end
return @root
end
def delete(text)
last = self.lastNode(text)
if (last != nil)
if (self.emptyNode(last))
self.deleteNode(text, @root, 0)
else
last.end = false
end
print("Delete Text " + text + "\n")
else
print("Not Exist Delete Text String :" + text + "\n")
end
end
end
def main()
obj = Trie.new()
obj.insert("cooky")
obj.insert("cool")
text = "cooky"
if (obj.search(text))
print("Exist :" + text + "\n")
else
print("Not Exist :" + text + "\n")
end
obj.delete("cooky")
if (obj.search(text))
print("Exist :" + text + "\n")
else
print("Not Exist :" + text + "\n")
end
end
main()
Output
Exist :cooky
Delete Text cooky
Not Exist :cooky
/*
Node JS program
Trie Deletion
*/
class Node {
constructor(size) {
this.end = false;
this.children = new Array(size).fill(null);
}
}
class Trie {
constructor() {
this.ALPHABETS = 26;
this.root = new Node(this.ALPHABETS);
}
search(text) {
var length = text.length;
var index = 0;
var head = this.root;
for (var level = 0; level < length; level++) {
index = text.charCodeAt(level) - 'a'.charCodeAt(0);
if (head.children[index] == null) {
return false;
}
head = head.children[index];
}
if (head != null && head.end == true) {
return true;
} else {
return false;
}
}
insert(text) {
var length = text.length;
var index = 0;
var head = this.root;
for (var level = 0; level < length; level++) {
index = text.charCodeAt(level) - 'a'.charCodeAt(0);
if (head.children[index] == null) {
head.children[index] = new Node(this.ALPHABETS);
}
head = head.children[index];
}
if (head != null) {
head.end = true;
}
}
emptyNode(root) {
for (var i = 0; i < this.ALPHABETS; i++) {
if (this.root.children[i] != null) {
return false;
}
}
return true;
}
lastNode(text) {
var length = text.length;
var index = 0;
var head = this.root;
for (var level = 0; level < length; level++) {
index = text.charCodeAt(level) - 'a'.charCodeAt(0);
if (head.children[index] == null) {
return null;
}
head = head.children[index];
}
if (head != null && head.end == true) {
return head;
} else {
return null;
}
}
deleteNode(text, root, level) {
if (this.root != null) {
if (level == text.Length) {
if (this.emptyNode(this.root)) {
return null;
}
return this.root;
}
var index = text.charCodeAt(level) - 'a'.charCodeAt(0);
this.root.children[index] = this.deleteNode(text, this.root.children[index], level + 1);
if (this.root.end == false && this.emptyNode(this.root)) {
return null;
}
}
return this.root;
}
delete(text) {
var last = this.lastNode(text);
if (last != null) {
if (this.emptyNode(last)) {
this.deleteNode(text, this.root, 0);
} else {
last.end = false;
}
console.log ("Delete Text " + text);
} else {
console.log ("Not Exist Delete Text String : " + text);
}
}
}
function main() {
var obj = new Trie();
obj.insert("cooky");
obj.insert("cool");
var text = "cooky";
if (obj.search(text)) {
console.log ("Exist : " + text);
} else {
console.log ("Not Exist : " + text);
}
obj.delete("cooky");
if (obj.search(text)) {
console.log ("Exist : " + text);
} else {
console.log ("Not Exist : " + text);
}
}
main();
Output
Exist : cooky
Delete Text cooky
Not Exist : cooky
Time Complexity Analysis
- The
search
operation has a time complexity of O(L), where L is the length of the string being searched. - The
insert
operation has a time complexity of O(L), similar to thesearch
operation. - The
delete
operation has a time complexity proportional to the length of the string being deleted, as it involves traversing the trie for the length of the string. Hence, its time complexity is also O(L).
Java code implemention

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