Posted on by Kalkicode
Code Tree

# Ternary Search Tree Deletion

The Ternary Search Tree (TST) is a specialized tree data structure that combines the characteristics of binary search trees and tries. It is particularly useful for storing and searching strings efficiently. TSTs are commonly used in applications that involve autocomplete suggestions, spell checking, and dictionary lookups. This article focuses on the deletion operation in Ternary Search Trees and provides a detailed explanation, code example, and output explanation.

## Problem Statement

The problem addressed here is how to implement the deletion operation in a Ternary Search Tree. Given a TST and a word, the goal is to remove the specified word from the tree while maintaining the properties of the TST, such as proper organization and efficient search capabilities.

## Example

Consider a Ternary Search Tree with the following words:

• co
• code
• fee
• feel
• milk
• run

We will demonstrate the deletion operation on this tree with different scenarios.

## Idea to Solve

To implement the deletion operation in a TST, we need to handle several cases:

1. The node to delete is in the left subtree.
2. The node to delete is in the right subtree.
3. The node to delete is in the equal subtree.
4. The node to delete is the last character of a word, but the word has other siblings.
5. The node to delete is the last character of a word, and the word has no other siblings.

## Pseudocode

1. Traverse the TST to find the node to delete.
2. Based on the relationships between nodes and the termination status of the word, determine the appropriate actions: a. If the node has a left child and the word's character is less than the node's data, move to the left subtree. b. If the node has a right child and the word's character is greater than the node's data, move to the right subtree. c. If the word's character matches the node's data: i. If the word has more characters, move to the equal subtree. ii. If the word has no more characters: - If the node is not a termination node, mark it as terminated. - If the node is a termination node, handle the different cases of deletion.
3. Recurse through the tree to delete nodes based on the cases mentioned above.

## Algorithm Explanation

1. Create the TST structure and necessary functions for insertion, traversal, and deletion.
2. Define the recursive function `deleteWord` that handles the deletion process. It will traverse the TST based on the characters of the word to delete.
3. Handle the cases of deleting nodes based on the relationships between nodes and the termination status of words.
4. Implement the `main` function where the TST is created, words are added, and deletion is demonstrated.
5. Print the TST before and after each deletion to observe the changes.

## Code Solution

``````// C program for
// Ternary Search Tree Deletion
#include <stdio.h>
#include <stdlib.h>

// Ternary search tree Node
struct TreeNode
{
char data;
int terminate;
struct TreeNode *left;
struct TreeNode *eq;
struct TreeNode *right;
};
struct TernarySearchTree
{
struct TreeNode *root;
};
// Create and return new tree
struct TernarySearchTree *newTree()
{
// Create a dynamic node
struct TernarySearchTree *tree =
(struct TernarySearchTree *) malloc(sizeof(struct TernarySearchTree));
if (tree != NULL)
{
tree->root = NULL;
}
else
{
printf("Memory Overflow to Create tree Tree\n");
exit(0);
}
// Return new tree
return tree;
}
// Create new node of tree
struct TreeNode *newTreeNode(char data)
{
struct TreeNode *node =
(struct TreeNode *) malloc(sizeof(struct TreeNode));
if (node == NULL)
{
// Memory overflow
exit(0);
}
node->left = NULL;
node->eq = NULL;
node->right = NULL;
node->data = data;
node->terminate = 0;
return node;
}
// A recursive function to traverse Ternary Search Tree
void traverseTSTUtil(struct TreeNode *node, char *output, int depth)
{
if (node != NULL)
{
// First traverse the left subtree
traverseTSTUtil(node->left, output, depth);
// Store the character of this node
output[depth] = node->data;
if (node->terminate)
{
output[depth + 1] = '\0';
printf(" %s\n", output);
}
// Traverse the subtree using equal pointer (middle subtree)
traverseTSTUtil(node->eq, output, depth + 1);
// Finally Traverse the right subtree
traverseTSTUtil(node->right, output, depth);
}
}
// Calculate height of tree
int treeHeight(struct TreeNode *node)
{
if (node != NULL)
{
// Find height of subtree using recursion
int a = treeHeight(node->left);
int b = treeHeight(node->right);
// Returns the height of largest subtree
if (a > b)
{
return a + 1;
}
else
{
return b + 1;
}
}
else
{
return 0;
}
}
void traverseTST(struct TreeNode *root)
{
if (root == NULL)
{
return;
}
int h = treeHeight(root) + 1;
char output[h];
traverseTSTUtil(root, output, 0);
}
// Function to insert a new word in a Ternary Search Tree
struct TreeNode *insert(struct TreeNode *root, char *word)
{
struct TreeNode *node = root;
if (root == NULL)
{
node = newTreeNode( *word);
}
if (( *word) < node->data)
{
node->left = insert(node->left, word);
}
else if (( *word) > node->data)
{
node->right = insert(node->right, word);
}
else
{
if ( *(word + 1))
{
node->eq = insert(node->eq, word + 1);
}
else
{
node->terminate = 1;
}
}
return node;
}
// Handles the request of add new node
void addNode(struct TernarySearchTree *tree, char *word)
{
tree->root = insert(tree->root, word);
}
int countSiblings(struct TreeNode *node)
{
int count = 0;
if (node->left != NULL)
{
count++;
}
if (node->right != NULL)
{
count++;
}
if (node->eq != NULL)
{
count++;
}
return count;
}
struct TreeNode *deleteWord(struct TreeNode *node, char *word)
{
if (node == NULL)
{
// When delete node not exist
return NULL;
}
int child = countSiblings(node);
if ( *word < node->data)
{
node->left = deleteWord(node->left, word);
}
else if ( *word > node->data)
{
node->right = deleteWord(node->right, word);
}
else
{
if ( *(word + 1))
{
// When word not empty
node->eq = deleteWord(node->eq, word + 1);
}
else if (node->terminate == 1)
{
if (child > 0)
{
// In case child node exist of deleted word
node->terminate = 0;
}
else
{
free(node);
return NULL;
}
}
}
if (child != countSiblings(node) && child == 1 && node->terminate == 0)
{
// When need to remove node
free(node);
return NULL;
}
return node;
}
int main()
{
struct TernarySearchTree *tree = newTree();
printf(" Ternary search tree\n");
traverseTST(tree->root);
// Case A
char *word = "fee";
printf("\n Delete word : %s \n", word);
tree->root = deleteWord(tree->root, word);
printf(" Ternary search tree\n");
traverseTST(tree->root);
// Case B
word = "code";
printf("\n Delete word : %s \n", word);
tree->root = deleteWord(tree->root, word);
printf(" Ternary search tree\n");
traverseTST(tree->root);
// Case C
word = "milks";
printf("\n Delete word : %s \n", word);
tree->root = deleteWord(tree->root, word);
printf(" Ternary search tree\n");
traverseTST(tree->root);
// Case D
word = "feel";
printf("\n Delete word : %s \n", word);
tree->root = deleteWord(tree->root, word);
printf(" Ternary search tree\n");
traverseTST(tree->root);
return 0;
}``````

#### input

`````` Ternary search tree
co
code
fee
feel
milk
run

Delete word : fee
Ternary search tree
co
code
feel
milk
run

Delete word : code
Ternary search tree
co
feel
milk
run

Delete word : milks
Ternary search tree
co
feel
milk
run

Delete word : feel
Ternary search tree
co
milk
run``````
``````/*
Java Program
Ternary Search Tree Deletion
*/
// Ternary search tree
class TreeNode
{
public char data;
public boolean terminate;
public TreeNode left;
public TreeNode equal;
public TreeNode right;
public TreeNode(char data)
{
this.data = data;
this.left = null;
this.right = null;
this.equal = null;
this.terminate = false;
}
}
public class TernarySearchTree
{
public TreeNode root;
public TernarySearchTree()
{
this.root = null;
}
// Print the all words using recursion
public void printWords(TreeNode node, String output, int depth)
{
if (node != null)
{
// Visit left subtree
printWords(node.left, output, depth);
if (node.terminate == true)
{
// Display word
System.out.print(" " + (output + node.data) + "\n");
}
// Visit equal (middle) subtree
printWords(node.equal, output + node.data, depth + 1);
// Visit left subtree
printWords(node.right, output, depth);
}
}
// Function to insert a new word in a Ternary Search Tree
public TreeNode insert(TreeNode rootNode, String word, int position)
{
TreeNode node = rootNode;
if (rootNode == null)
{
node = new TreeNode(word.charAt(position));
}
if (word.charAt(position) < node.data)
{
node.left = insert(node.left, word, position);
}
else if (word.charAt(position) > node.data)
{
node.right = insert(node.right, word, position);
}
else
{
if ((position + 1) < word.length())
{
node.equal = insert(node.equal, word, position + 1);
}
else
{
node.terminate = true;
}
}
return node;
}
// Handles the request of add new node
{
if (word.length() == 0)
{
return;
}
this.root = insert(this.root, word, 0);
}
public boolean searchElement(TreeNode node, String word, int position)
{
if (node == null)
{
return false;
}
else if (word.charAt(position) < node.data)
{
return searchElement(node.left, word, position);
}
else if (word.charAt(position) > node.data)
{
return searchElement(node.right, word, position);
}
else
{
if (position + 1 < word.length())
{
// When word not empty
return searchElement(node.equal, word, position + 1);
}
else
{
// returns status to terminate word
return node.terminate;
}
}
}
// Handles the request of search word
public void searchTreeNode(String word)
{
System.out.print("\n Given : [" + word + "] \n");
if (word.length() > 0
&& this.searchElement(root, word, 0) == true)
{
System.out.print(" Found\n");
}
else
{
}
}
public int countSiblings(TreeNode node)
{
int count = 0;
if (node.left != null)
{
count++;
}
if (node.right != null)
{
count++;
}
if (node.equal != null)
{
count++;
}
return count;
}
public TreeNode deleteWord(TreeNode node, String word, int position)
{
if (node == null)
{
// When delete node not exist
return null;
}
int child = countSiblings(node);
if (word.charAt(position) < node.data)
{
node.left = deleteWord(node.left, word, position);
}
else if (word.charAt(position) > node.data)
{
node.right = deleteWord(node.right, word, position);
}
else
{
if ((position + 1) < word.length())
{
// When word not empty
node.equal = deleteWord(node.equal, word, position + 1);
}
else if (node.terminate == true)
{
if (child > 0)
{
// In case child node exist of deleted word
node.terminate = false;
}
else
{
return null;
}
}
}
if (child != countSiblings(node)
&& child == 1 && node.terminate == false)
{
// When need to remove node
return null;
}
return node;
}
public static void main(String[] args)
{
TernarySearchTree tree = new TernarySearchTree();
System.out.print(" Ternary search tree\n");
tree.printWords(tree.root, "", 0);
// Case A
String word = "fee";
System.out.print("\n Delete word : " + word + " \n");
tree.root = tree.deleteWord(tree.root, word, 0);
System.out.print(" Ternary search tree\n");
tree.printWords(tree.root, "", 0);
// Case B
word = "code";
System.out.print("\n Delete word : " + word + " \n");
tree.root = tree.deleteWord(tree.root, word, 0);
System.out.print(" Ternary search tree\n");
tree.printWords(tree.root, "", 0);
// Case C
word = "milks";
System.out.print("\n Delete word : " + word + " \n");
tree.root = tree.deleteWord(tree.root, word, 0);
System.out.print(" Ternary search tree\n");
tree.printWords(tree.root, "", 0);
// Case D
word = "feel";
System.out.print("\n Delete word : " + word + " \n");
tree.root = tree.deleteWord(tree.root, word, 0);
System.out.print(" Ternary search tree\n");
tree.printWords(tree.root, "", 0);
}
}``````

#### input

`````` Ternary search tree
co
code
fee
feel
milk
run

Delete word : fee
Ternary search tree
co
code
feel
milk
run

Delete word : code
Ternary search tree
co
feel
milk
run

Delete word : milks
Ternary search tree
co
feel
milk
run

Delete word : feel
Ternary search tree
co
milk
run``````
``````// Include namespace system
using System;
/*
Csharp Program
Ternary Search Tree Deletion
*/
// Ternary search tree
public class TreeNode
{
public char data;
public Boolean terminate;
public TreeNode left;
public TreeNode equal;
public TreeNode right;
public TreeNode(char data)
{
this.data = data;
this.left = null;
this.right = null;
this.equal = null;
this.terminate = false;
}
}
public class TernarySearchTree
{
public TreeNode root;
public TernarySearchTree()
{
this.root = null;
}
// Print the all words using recursion
public void printWords(TreeNode node, String output, int depth)
{
if (node != null)
{
// Visit left subtree
this.printWords(node.left, output, depth);
if (node.terminate == true)
{
// Display word
Console.Write(" " + (output + node.data) + "\n");
}
// Visit equal (middle) subtree
this.printWords(node.equal, output + node.data, depth + 1);
// Visit left subtree
this.printWords(node.right, output, depth);
}
}
// Function to insert a new word in a Ternary Search Tree
public TreeNode insert(TreeNode rootNode, String word, int position)
{
TreeNode node = rootNode;
if (rootNode == null)
{
node = new TreeNode(word[position]);
}
if (word[position] < node.data)
{
node.left = this.insert(node.left, word, position);
}
else if (word[position] > node.data)
{
node.right = this.insert(node.right, word, position);
}
else
{
if ((position + 1) < word.Length)
{
node.equal = this.insert(node.equal, word, position + 1);
}
else
{
node.terminate = true;
}
}
return node;
}
// Handles the request of add new node
{
if (word.Length == 0)
{
return;
}
this.root = this.insert(this.root, word, 0);
}
public Boolean searchElement(TreeNode node, String word, int position)
{
if (node == null)
{
return false;
}
else if (word[position] < node.data)
{
return this.searchElement(node.left, word, position);
}
else if (word[position] > node.data)
{
return this.searchElement(node.right, word, position);
}
else
{
if (position + 1 < word.Length)
{
// When word not empty
return this.searchElement(node.equal, word, position + 1);
}
else
{
// returns status to terminate word
return node.terminate;
}
}
}
// Handles the request of search word
public void searchTreeNode(String word)
{
Console.Write("\n Given : [" + word + "] \n");
if (word.Length > 0 && this.searchElement(this.root, word, 0) == true)
{
Console.Write(" Found\n");
}
else
{
}
}
public int countSiblings(TreeNode node)
{
int count = 0;
if (node.left != null)
{
count++;
}
if (node.right != null)
{
count++;
}
if (node.equal != null)
{
count++;
}
return count;
}
public TreeNode deleteWord(TreeNode node, String word, int position)
{
if (node == null)
{
// When delete node not exist
return null;
}
int child = this.countSiblings(node);
if (word[position] < node.data)
{
node.left = this.deleteWord(node.left, word, position);
}
else if (word[position] > node.data)
{
node.right = this.deleteWord(node.right, word, position);
}
else
{
if ((position + 1) < word.Length)
{
// When word not empty
node.equal = this.deleteWord(node.equal, word, position + 1);
}
else if (node.terminate == true)
{
if (child > 0)
{
// In case child node exist of deleted word
node.terminate = false;
}
else
{
return null;
}
}
}
if (child != this.countSiblings(node)
&& child == 1 && node.terminate == false)
{
// When need to remove node
return null;
}
return node;
}
public static void Main(String[] args)
{
TernarySearchTree tree = new TernarySearchTree();
Console.Write(" Ternary search tree\n");
tree.printWords(tree.root, "", 0);
// Case A
String word = "fee";
Console.Write("\n Delete word : " + word + " \n");
tree.root = tree.deleteWord(tree.root, word, 0);
Console.Write(" Ternary search tree\n");
tree.printWords(tree.root, "", 0);
// Case B
word = "code";
Console.Write("\n Delete word : " + word + " \n");
tree.root = tree.deleteWord(tree.root, word, 0);
Console.Write(" Ternary search tree\n");
tree.printWords(tree.root, "", 0);
// Case C
word = "milks";
Console.Write("\n Delete word : " + word + " \n");
tree.root = tree.deleteWord(tree.root, word, 0);
Console.Write(" Ternary search tree\n");
tree.printWords(tree.root, "", 0);
// Case D
word = "feel";
Console.Write("\n Delete word : " + word + " \n");
tree.root = tree.deleteWord(tree.root, word, 0);
Console.Write(" Ternary search tree\n");
tree.printWords(tree.root, "", 0);
}
}``````

#### input

`````` Ternary search tree
co
code
fee
feel
milk
run

Delete word : fee
Ternary search tree
co
code
feel
milk
run

Delete word : code
Ternary search tree
co
feel
milk
run

Delete word : milks
Ternary search tree
co
feel
milk
run

Delete word : feel
Ternary search tree
co
milk
run``````
``````// Include header file
#include <iostream>

#include <string>

using namespace std;
/*
C++ Program
Ternary Search Tree Deletion
*/
// Ternary search tree
class TreeNode
{
public: char data;
bool terminate;
TreeNode *left;
TreeNode *equal;
TreeNode *right;
TreeNode()
{
this->left = NULL;
this->right = NULL;
this->equal = NULL;
}
TreeNode(char data)
{
this->data = data;
this->left = NULL;
this->right = NULL;
this->equal = NULL;
this->terminate = false;
}
};
class TernarySearchTree
{
public: TreeNode *root;
TernarySearchTree()
{
this->root = NULL;
}
// Print the all words using recursion
void printWords(TreeNode *node, string output, int depth)
{
if (node != NULL)
{
// Visit left subtree
this->printWords(node->left, output, depth);
if (node->terminate == true)
{
// Display word
cout << " " << (output + node->data) << "\n";
}
// Visit equal (middle) subtree
this->printWords(node->equal, output + node->data, depth + 1);
// Visit left subtree
this->printWords(node->right, output, depth);
}
}
// Function to insert a new word in a Ternary Search Tree
TreeNode *insert(TreeNode *rootNode, string word, int position)
{
TreeNode *node = rootNode;
if (rootNode == NULL)
{
node = new TreeNode(word[position]);
}
if (word[position] < node->data)
{
node->left = this->insert(node->left, word, position);
}
else if (word[position] > node->data)
{
node->right = this->insert(node->right, word, position);
}
else
{
if ((position + 1) < word.length())
{
node->equal = this->insert(node->equal, word, position + 1);
}
else
{
node->terminate = true;
}
}
return node;
}
// Handles the request of add new node
{
if (word.length() == 0)
{
return;
}
this->root = this->insert(this->root, word, 0);
}
bool searchElement(TreeNode *node, string word, int position)
{
if (node == NULL)
{
return false;
}
else if (word[position] < node->data)
{
return this->searchElement(node->left, word, position);
}
else if (word[position] > node->data)
{
return this->searchElement(node->right, word, position);
}
else
{
if (position + 1 < word.length())
{
// When word not empty
return this->searchElement(node->equal, word, position + 1);
}
else
{
// returns status to terminate word
return node->terminate;
}
}
}
// Handles the request of search word
void searchTreeNode(string word)
{
cout << "\n Given : [" << word << "] \n";
if (word.length() > 0
&& this->searchElement(this->root, word, 0) == true)
{
cout << " Found\n";
}
else
{
}
}
int countSiblings(TreeNode *node)
{
int count = 0;
if (node->left != NULL)
{
count++;
}
if (node->right != NULL)
{
count++;
}
if (node->equal != NULL)
{
count++;
}
return count;
}
TreeNode *deleteWord(TreeNode *node, string word, int position)
{
if (node == NULL)
{
// When delete node not exist
return NULL;
}
int child = this->countSiblings(node);
if (word[position] < node->data)
{
node->left = this->deleteWord(node->left, word, position);
}
else if (word[position] > node->data)
{
node->right = this->deleteWord(node->right, word, position);
}
else
{
if ((position + 1) < word.length())
{
// When word not empty
node->equal = this->deleteWord(node->equal, word, position + 1);
}
else if (node->terminate == true)
{
if (child > 0)
{
// In case child node exist of deleted word
node->terminate = false;
}
else
{
delete node;
return NULL;
}
}
}
if (child != this->countSiblings(node)
&& child == 1 && node->terminate == false)
{
delete node;
// When need to remove node
return NULL;
}
return node;
}
};
int main()
{
TernarySearchTree *tree = new TernarySearchTree();
cout << " Ternary search tree\n";
tree->printWords(tree->root, "", 0);
// Case A
string word = "fee";
cout << "\n Delete word : " << word << " \n";
tree->root = tree->deleteWord(tree->root, word, 0);
cout << " Ternary search tree\n";
tree->printWords(tree->root, "", 0);
// Case B
word = "code";
cout << "\n Delete word : " << word << " \n";
tree->root = tree->deleteWord(tree->root, word, 0);
cout << " Ternary search tree\n";
tree->printWords(tree->root, "", 0);
// Case C
word = "milks";
cout << "\n Delete word : " << word << " \n";
tree->root = tree->deleteWord(tree->root, word, 0);
cout << " Ternary search tree\n";
tree->printWords(tree->root, "", 0);
// Case D
word = "feel";
cout << "\n Delete word : " << word << " \n";
tree->root = tree->deleteWord(tree->root, word, 0);
cout << " Ternary search tree\n";
tree->printWords(tree->root, "", 0);
return 0;
}``````

#### input

`````` Ternary search tree
co
code
fee
feel
milk
run

Delete word : fee
Ternary search tree
co
code
feel
milk
run

Delete word : code
Ternary search tree
co
feel
milk
run

Delete word : milks
Ternary search tree
co
feel
milk
run

Delete word : feel
Ternary search tree
co
milk
run``````
``````<?php
/*
Php Program
Ternary Search Tree Deletion
*/
// Ternary search tree
class TreeNode
{
public \$data;
public \$terminate;
public \$left;
public \$equal;
public \$right;
public	function __construct(\$data)
{
\$this->data = \$data;
\$this->left = NULL;
\$this->right = NULL;
\$this->equal = NULL;
\$this->terminate = false;
}
}
class TernarySearchTree
{
public \$root;
public	function __construct()
{
\$this->root = NULL;
}
// Print the all words using recursion
public	function printWords(\$node, \$output, \$depth)
{
if (\$node != NULL)
{
// Visit left subtree
\$this->printWords(\$node->left, \$output, \$depth);
if (\$node->terminate == true)
{
// Display word
echo(" ".(\$output.\$node->data).
"\n");
}
// Visit equal (middle) subtree
\$this->printWords(\$node->equal,
\$output.strval(\$node->data), \$depth + 1);
// Visit left subtree
\$this->printWords(\$node->right, \$output, \$depth);
}
}
// Function to insert a new word in a Ternary Search Tree
public	function insert(\$rootNode, \$word, \$position)
{
\$node = \$rootNode;
if (\$rootNode == NULL)
{
\$node = new TreeNode(\$word[\$position]);
}
if (\$word[\$position] < \$node->data)
{
\$node->left = \$this->insert(\$node->left, \$word, \$position);
}
else if (\$word[\$position] > \$node->data)
{
\$node->right = \$this->insert(\$node->right, \$word, \$position);
}
else
{
if ((\$position + 1) < strlen(\$word))
{
\$node->equal = \$this->insert(\$node->equal, \$word, \$position + 1);
}
else
{
\$node->terminate = true;
}
}
return \$node;
}
// Handles the request of add new node
{
if (strlen(\$word) == 0)
{
return;
}
\$this->root = \$this->insert(\$this->root, \$word, 0);
}
public	function searchElement(\$node, \$word, \$position)
{
if (\$node == NULL)
{
return false;
}
else if (\$word[\$position] < \$node->data)
{
return \$this->searchElement(\$node->left, \$word, \$position);
}
else if (\$word[\$position] > \$node->data)
{
return \$this->searchElement(\$node->right, \$word, \$position);
}
else
{
if (\$position + 1 < strlen(\$word))
{
// When word not empty
return \$this->searchElement(\$node->equal, \$word, \$position + 1);
}
else
{
// returns status to terminate word
return \$node->terminate;
}
}
}
// Handles the request of search word
public	function searchTreeNode(\$word)
{
echo("\n Given : [".\$word.
"] \n");
if (strlen(\$word) > 0
&& \$this->searchElement(\$this->root, \$word, 0) == true)
{
echo(" Found\n");
}
else
{
}
}
public	function countSiblings(\$node)
{
\$count = 0;
if (\$node->left != NULL)
{
\$count++;
}
if (\$node->right != NULL)
{
\$count++;
}
if (\$node->equal != NULL)
{
\$count++;
}
return \$count;
}
public	function deleteWord(\$node, \$word, \$position)
{
if (\$node == NULL)
{
// When delete node not exist
return NULL;
}
\$child = \$this->countSiblings(\$node);
if (\$word[\$position] < \$node->data)
{
\$node->left = \$this->deleteWord(\$node->left, \$word, \$position);
}
else if (\$word[\$position] > \$node->data)
{
\$node->right = \$this->deleteWord(\$node->right, \$word, \$position);
}
else
{
if ((\$position + 1) < strlen(\$word))
{
// When word not empty
\$node->equal = \$this->deleteWord(\$node->equal, \$word, \$position + 1);
}
else if (\$node->terminate == true)
{
if (\$child > 0)
{
// In case child node exist of deleted word
\$node->terminate = false;
}
else
{
return NULL;
}
}
}
if (\$child != \$this->countSiblings(\$node)
&& \$child == 1 && \$node->terminate == false)
{
// When need to remove node
return NULL;
}
return \$node;
}
}

function main()
{
\$tree = new TernarySearchTree();
echo(" Ternary search tree\n");
\$tree->printWords(\$tree->root, "", 0);
// Case A
\$word = "fee";
echo("\n Delete word : ".\$word.
" \n");
\$tree->root = \$tree->deleteWord(\$tree->root, \$word, 0);
echo(" Ternary search tree\n");
\$tree->printWords(\$tree->root, "", 0);
// Case B
\$word = "code";
echo("\n Delete word : ".\$word.
" \n");
\$tree->root = \$tree->deleteWord(\$tree->root, \$word, 0);
echo(" Ternary search tree\n");
\$tree->printWords(\$tree->root, "", 0);
// Case C
\$word = "milks";
echo("\n Delete word : ".\$word.
" \n");
\$tree->root = \$tree->deleteWord(\$tree->root, \$word, 0);
echo(" Ternary search tree\n");
\$tree->printWords(\$tree->root, "", 0);
// Case D
\$word = "feel";
echo("\n Delete word : ".\$word.
" \n");
\$tree->root = \$tree->deleteWord(\$tree->root, \$word, 0);
echo(" Ternary search tree\n");
\$tree->printWords(\$tree->root, "", 0);
}
main();``````

#### input

`````` Ternary search tree
co
code
fee
feel
milk
run

Delete word : fee
Ternary search tree
co
code
feel
milk
run

Delete word : code
Ternary search tree
co
feel
milk
run

Delete word : milks
Ternary search tree
co
feel
milk
run

Delete word : feel
Ternary search tree
co
milk
run``````
``````/*
Node JS Program
Ternary Search Tree Deletion
*/
// Ternary search tree
class TreeNode
{
constructor(data)
{
this.data = data;
this.left = null;
this.right = null;
this.equal = null;
this.terminate = false;
}
}
class TernarySearchTree
{
constructor()
{
this.root = null;
}
// Print the all words using recursion
printWords(node, output, depth)
{
if (node != null)
{
// Visit left subtree
this.printWords(node.left, output, depth);
if (node.terminate == true)
{
// Display word
process.stdout.write(" " + (output + node.data) + "\n");
}
// Visit equal (middle) subtree
this.printWords(node.equal, output + node.data, depth + 1);
// Visit left subtree
this.printWords(node.right, output, depth);
}
}
// Function to insert a new word in a Ternary Search Tree
insert(rootNode, word, position)
{
var node = rootNode;
if (rootNode == null)
{
node = new TreeNode(word.charAt(position));
}
if (word.charAt(position) < node.data)
{
node.left = this.insert(node.left, word, position);
}
else if (word.charAt(position) > node.data)
{
node.right = this.insert(node.right, word, position);
}
else
{
if ((position + 1) < word.length)
{
node.equal = this.insert(node.equal, word, position + 1);
}
else
{
node.terminate = true;
}
}
return node;
}
// Handles the request of add new node
{
if (word.length == 0)
{
return;
}
this.root = this.insert(this.root, word, 0);
}
searchElement(node, word, position)
{
if (node == null)
{
return false;
}
else if (word.charAt(position) < node.data)
{
return this.searchElement(node.left, word, position);
}
else if (word.charAt(position) > node.data)
{
return this.searchElement(node.right, word, position);
}
else
{
if (position + 1 < word.length)
{
// When word not empty
return this.searchElement(node.equal, word, position + 1);
}
else
{
// returns status to terminate word
return node.terminate;
}
}
}
// Handles the request of search word
searchTreeNode(word)
{
process.stdout.write("\n Given : [" + word + "] \n");
if (word.length > 0
&& this.searchElement(this.root, word, 0) == true)
{
process.stdout.write(" Found\n");
}
else
{
}
}
countSiblings(node)
{
var count = 0;
if (node.left != null)
{
count++;
}
if (node.right != null)
{
count++;
}
if (node.equal != null)
{
count++;
}
return count;
}
deleteWord(node, word, position)
{
if (node == null)
{
// When delete node not exist
return null;
}
var child = this.countSiblings(node);
if (word.charAt(position) < node.data)
{
node.left = this.deleteWord(node.left, word, position);
}
else if (word.charAt(position) > node.data)
{
node.right = this.deleteWord(node.right, word, position);
}
else
{
if ((position + 1) < word.length)
{
// When word not empty
node.equal = this.deleteWord(node.equal, word, position + 1);
}
else if (node.terminate == true)
{
if (child > 0)
{
// In case child node exist of deleted word
node.terminate = false;
}
else
{
return null;
}
}
}
if (child != this.countSiblings(node)
&& child == 1 && node.terminate == false)
{
// When need to remove node
return null;
}
return node;
}
}

function main()
{
var tree = new TernarySearchTree();
process.stdout.write(" Ternary search tree\n");
tree.printWords(tree.root, "", 0);
// Case A
var word = "fee";
process.stdout.write("\n Delete word : " + word + " \n");
tree.root = tree.deleteWord(tree.root, word, 0);
process.stdout.write(" Ternary search tree\n");
tree.printWords(tree.root, "", 0);
// Case B
word = "code";
process.stdout.write("\n Delete word : " + word + " \n");
tree.root = tree.deleteWord(tree.root, word, 0);
process.stdout.write(" Ternary search tree\n");
tree.printWords(tree.root, "", 0);
// Case C
word = "milks";
process.stdout.write("\n Delete word : " + word + " \n");
tree.root = tree.deleteWord(tree.root, word, 0);
process.stdout.write(" Ternary search tree\n");
tree.printWords(tree.root, "", 0);
// Case D
word = "feel";
process.stdout.write("\n Delete word : " + word + " \n");
tree.root = tree.deleteWord(tree.root, word, 0);
process.stdout.write(" Ternary search tree\n");
tree.printWords(tree.root, "", 0);
}
main();``````

#### input

`````` Ternary search tree
co
code
fee
feel
milk
run

Delete word : fee
Ternary search tree
co
code
feel
milk
run

Delete word : code
Ternary search tree
co
feel
milk
run

Delete word : milks
Ternary search tree
co
feel
milk
run

Delete word : feel
Ternary search tree
co
milk
run``````
``````#    Python 3 Program
#    Ternary Search Tree Deletion

#  Ternary search tree
class TreeNode :
def __init__(self, data) :
self.data = data
self.left = None
self.right = None
self.equal = None
self.terminate = False

class TernarySearchTree :
def __init__(self) :
self.root = None

#  Print the all words using recursion
def printWords(self, node, output, depth) :
if (node != None) :
#  Visit left subtree
self.printWords(node.left, output, depth)
if (node.terminate == True) :
#  Display word
print(" ", (output + node.data) )

#  Visit equal (middle) subtree
self.printWords(node.equal,
output + str(node.data),
depth + 1)
#  Visit left subtree
self.printWords(node.right, output, depth)

#  Function to insert a new word in a Ternary Search Tree
def insert(self, rootNode, word, position) :
node = rootNode
if (rootNode == None) :
node = TreeNode(word[position])

if (word[position] < node.data) :
node.left = self.insert(node.left, word, position)
elif (word[position] > node.data) :
node.right = self.insert(node.right, word, position)
else :
if ((position + 1) < len(word)) :
node.equal = self.insert(node.equal, word, position + 1)
else :
node.terminate = True

return node

#  Handles the request of add new node
if (len(word) == 0) :
return

self.root = self.insert(self.root, word, 0)

def searchElement(self, node, word, position) :
if (node == None) :
return False
elif (word[position] < node.data) :
return self.searchElement(node.left, word, position)
elif (word[position] > node.data) :
return self.searchElement(node.right, word, position)
else :
if (position + 1 < len(word)) :
#  When word not empty
return self.searchElement(node.equal, word, position + 1)
else :
#  returns status to terminate word
return node.terminate

#  Handles the request of search word
def searchTreeNode(self, word) :
print("\n Given : [", word ,"] ")
if (len(word) > 0 and
self.searchElement(self.root, word, 0) == True) :
print(" Found")
else :

def countSiblings(self, node) :
count = 0
if (node.left != None) :
count += 1

if (node.right != None) :
count += 1

if (node.equal != None) :
count += 1

return count

def deleteWord(self, node, word, position) :
if (node == None) :
#  When delete node not exist
return None

child = self.countSiblings(node)
if (word[position] < node.data) :
node.left = self.deleteWord(node.left, word, position)
elif (word[position] > node.data) :
node.right = self.deleteWord(node.right, word, position)
else :
if ((position + 1) < len(word)) :
#  When word not empty
node.equal = self.deleteWord(node.equal, word, position + 1)
elif (node.terminate == True) :
if (child > 0) :
#  In case child node exist of deleted word
node.terminate = False
else :
return None

if (child != self.countSiblings(node) and child == 1 and node.terminate == False) :
#  When need to remove node
return None

return node

def main() :
tree = TernarySearchTree()
print(" Ternary search tree")
tree.printWords(tree.root, "", 0)
#  Case A
word = "fee"
print("\n Delete word : ", word ," ")
tree.root = tree.deleteWord(tree.root, word, 0)
print(" Ternary search tree")
tree.printWords(tree.root, "", 0)
#  Case B
word = "code"
print("\n Delete word : ", word ," ")
tree.root = tree.deleteWord(tree.root, word, 0)
print(" Ternary search tree")
tree.printWords(tree.root, "", 0)
#  Case C
word = "milks"
print("\n Delete word : ", word ," ")
tree.root = tree.deleteWord(tree.root, word, 0)
print(" Ternary search tree")
tree.printWords(tree.root, "", 0)
#  Case D
word = "feel"
print("\n Delete word : ", word ," ")
tree.root = tree.deleteWord(tree.root, word, 0)
print(" Ternary search tree")
tree.printWords(tree.root, "", 0)

if __name__ == "__main__": main()``````

#### input

`````` Ternary search tree
co
code
fee
feel
milk
run

Delete word :  fee
Ternary search tree
co
code
feel
milk
run

Delete word :  code
Ternary search tree
co
feel
milk
run

Delete word :  milks
Ternary search tree
co
feel
milk
run

Delete word :  feel
Ternary search tree
co
milk
run``````
``````#    Ruby Program
#    Ternary Search Tree Deletion

#  Ternary search tree
class TreeNode
# Define the accessor and reader of class TreeNode
attr_reader :data, :terminate, :left, :equal, :right
attr_accessor :data, :terminate, :left, :equal, :right
def initialize(data)
self.data = data
self.left = nil
self.right = nil
self.equal = nil
self.terminate = false
end

end

class TernarySearchTree
# Define the accessor and reader of class TernarySearchTree
attr_accessor :root
def initialize()
self.root = nil
end

#  Print the all words using recursion
def printWords(node, output, depth)
if (node != nil)
#  Visit left subtree
self.printWords(node.left, output, depth)
if (node.terminate == true)
#  Display word
print(" ", (output + node.data) ,"\n")
end

#  Visit equal (middle) subtree
self.printWords(node.equal, output + node.data.to_s, depth + 1)
#  Visit left subtree
self.printWords(node.right, output, depth)
end

end

#  Function to insert a new word in a Ternary Search Tree
def insert(rootNode, word, position)
node = rootNode
if (rootNode == nil)
node = TreeNode.new(word[position])
end

if (word[position] < node.data)
node.left = self.insert(node.left, word, position)
elsif (word[position] > node.data)
node.right = self.insert(node.right, word, position)
else

if ((position + 1) < word.length)
node.equal = self.insert(node.equal, word, position + 1)
else

node.terminate = true
end

end

return node
end

#  Handles the request of add new node
if (word.length == 0)
return
end

self.root = self.insert(self.root, word, 0)
end

def searchElement(node, word, position)
if (node == nil)
return false
elsif (word[position] < node.data)
return self.searchElement(node.left, word, position)
elsif (word[position] > node.data)
return self.searchElement(node.right, word, position)
else

if (position + 1 < word.length)
#  When word not empty
return self.searchElement(node.equal, word, position + 1)
else

#  returns status to terminate word
return node.terminate
end

end

end

#  Handles the request of search word
def searchTreeNode(word)
print("\n Given : [", word ,"] \n")
if (word.length > 0 && self.searchElement(self.root, word, 0) == true)
print(" Found\n")
else

end

end

def countSiblings(node)
count = 0
if (node.left != nil)
count += 1
end

if (node.right != nil)
count += 1
end

if (node.equal != nil)
count += 1
end

return count
end

def deleteWord(node, word, position)
if (node == nil)
#  When delete node not exist
return nil
end

child = self.countSiblings(node)
if (word[position] < node.data)
node.left = self.deleteWord(node.left, word, position)
elsif (word[position] > node.data)
node.right = self.deleteWord(node.right, word, position)
else

if ((position + 1) < word.length)
#  When word not empty
node.equal = self.deleteWord(node.equal, word, position + 1)
elsif (node.terminate == true)
if (child > 0)
#  In case child node exist of deleted word
node.terminate = false
else

return nil
end

end

end

if (child != self.countSiblings(node) &&
child == 1 && node.terminate == false)
#  When need to remove node
return nil
end

return node
end

end

def main()
tree = TernarySearchTree.new()
print(" Ternary search tree\n")
tree.printWords(tree.root, "", 0)
#  Case A
word = "fee"
print("\n Delete word : ", word ," \n")
tree.root = tree.deleteWord(tree.root, word, 0)
print(" Ternary search tree\n")
tree.printWords(tree.root, "", 0)
#  Case B
word = "code"
print("\n Delete word : ", word ," \n")
tree.root = tree.deleteWord(tree.root, word, 0)
print(" Ternary search tree\n")
tree.printWords(tree.root, "", 0)
#  Case C
word = "milks"
print("\n Delete word : ", word ," \n")
tree.root = tree.deleteWord(tree.root, word, 0)
print(" Ternary search tree\n")
tree.printWords(tree.root, "", 0)
#  Case D
word = "feel"
print("\n Delete word : ", word ," \n")
tree.root = tree.deleteWord(tree.root, word, 0)
print(" Ternary search tree\n")
tree.printWords(tree.root, "", 0)
end

main()``````

#### input

`````` Ternary search tree
co
code
fee
feel
milk
run

Delete word : fee
Ternary search tree
co
code
feel
milk
run

Delete word : code
Ternary search tree
co
feel
milk
run

Delete word : milks
Ternary search tree
co
feel
milk
run

Delete word : feel
Ternary search tree
co
milk
run
``````
``````import scala.collection.mutable._;
/*
Scala Program
Ternary Search Tree Deletion
*/
// Ternary search tree
class TreeNode(var data: Char,
var terminate: Boolean,
var left: TreeNode,
var equal: TreeNode,
var right: TreeNode)
{
def this(data: Char)
{
this(data,false,null,null,null);
}
}
class TernarySearchTree(var root: TreeNode)
{
def this()
{
this(null);
}
// Print the all words using recursion
def printWords(node: TreeNode, output: String, depth: Int): Unit = {
if (node != null)
{
// Visit left subtree
printWords(node.left, output, depth);
if (node.terminate == true)
{
// Display word
print(" " + (output + node.data) + "\n");
}
// Visit equal (middle) subtree
printWords(node.equal,
output + node.data.toString(),
depth + 1);
// Visit left subtree
printWords(node.right, output, depth);
}
}
// Function to insert a new word in a Ternary Search Tree
def insert(rootNode: TreeNode, word: String, position: Int): TreeNode = {
var node: TreeNode = rootNode;
if (rootNode == null)
{
node = new TreeNode(word.charAt(position));
}
if (word.charAt(position) < node.data)
{
node.left = insert(node.left, word, position);
}
else if (word.charAt(position) > node.data)
{
node.right = insert(node.right, word, position);
}
else
{
if ((position + 1) < word.length())
{
node.equal = insert(node.equal, word, position + 1);
}
else
{
node.terminate = true;
}
}
return node;
}
// Handles the request of add new node
def addNode(word: String): Unit = {
if (word.length() == 0)
{
return;
}
this.root = insert(this.root, word, 0);
}
def searchElement(node: TreeNode, word: String, position: Int): Boolean = {
if (node == null)
{
return false;
}
else if (word.charAt(position) < node.data)
{
return searchElement(node.left, word, position);
}
else if (word.charAt(position) > node.data)
{
return searchElement(node.right, word, position);
}
else
{
if (position + 1 < word.length())
{
// When word not empty
return searchElement(node.equal, word, position + 1);
}
else
{
// returns status to terminate word
return node.terminate;
}
}
}
// Handles the request of search word
def searchTreeNode(word: String): Unit = {
print("\n Given : [" + word + "] \n");
if (word.length() > 0 &&
this.searchElement(root, word, 0) == true)
{
print(" Found\n");
}
else
{
}
}
def countSiblings(node: TreeNode): Int = {
var count: Int = 0;
if (node.left != null)
{
count += 1;
}
if (node.right != null)
{
count += 1;
}
if (node.equal != null)
{
count += 1;
}
return count;
}
def deleteWord(node: TreeNode, word: String, position: Int): TreeNode = {
if (node == null)
{
// When delete node not exist
return null;
}
var child: Int = countSiblings(node);
if (word.charAt(position) < node.data)
{
node.left = deleteWord(node.left, word, position);
}
else if (word.charAt(position) > node.data)
{
node.right = deleteWord(node.right, word, position);
}
else
{
if ((position + 1) < word.length())
{
// When word not empty
node.equal = deleteWord(node.equal, word, position + 1);
}
else if (node.terminate == true)
{
if (child > 0)
{
// In case child node exist of deleted word
node.terminate = false;
}
else
{
return null;
}
}
}
if (child != countSiblings(node) &&
child == 1 && node.terminate == false)
{
// When need to remove node
return null;
}
return node;
}
}
object Main
{
def main(args: Array[String]): Unit = {
var tree: TernarySearchTree = new TernarySearchTree();
print(" Ternary search tree\n");
tree.printWords(tree.root, "", 0);
// Case A
var word: String = "fee";
print("\n Delete word : " + word + " \n");
tree.root = tree.deleteWord(tree.root, word, 0);
print(" Ternary search tree\n");
tree.printWords(tree.root, "", 0);
// Case B
word = "code";
print("\n Delete word : " + word + " \n");
tree.root = tree.deleteWord(tree.root, word, 0);
print(" Ternary search tree\n");
tree.printWords(tree.root, "", 0);
// Case C
word = "milks";
print("\n Delete word : " + word + " \n");
tree.root = tree.deleteWord(tree.root, word, 0);
print(" Ternary search tree\n");
tree.printWords(tree.root, "", 0);
// Case D
word = "feel";
print("\n Delete word : " + word + " \n");
tree.root = tree.deleteWord(tree.root, word, 0);
print(" Ternary search tree\n");
tree.printWords(tree.root, "", 0);
}
}``````

#### input

`````` Ternary search tree
co
code
fee
feel
milk
run

Delete word : fee
Ternary search tree
co
code
feel
milk
run

Delete word : code
Ternary search tree
co
feel
milk
run

Delete word : milks
Ternary search tree
co
feel
milk
run

Delete word : feel
Ternary search tree
co
milk
run``````
``````/*
Kotlin Program
Ternary Search Tree Deletion
*/
// Ternary search tree
class TreeNode
{
var data: Char;
var terminate: Boolean;
var left: TreeNode ? ;
var equal: TreeNode ? ;
var right: TreeNode ? ;
constructor(data: Char)
{
this.data = data;
this.left = null;
this.right = null;
this.equal = null;
this.terminate = false;
}
}
class TernarySearchTree
{
var root: TreeNode ? ;
constructor()
{
this.root = null;
}
// Print the all words using recursion
fun printWords(node: TreeNode ? , output : String, depth: Int): Unit
{
if (node != null)
{
// Visit left subtree
this.printWords(node.left, output, depth);
if (node.terminate == true)
{
// Display word
print(" " + (output + node.data) + "\n");
}
// Visit equal (middle) subtree
this.printWords(node.equal,
output + node.data.toString(),
depth + 1);
// Visit left subtree
this.printWords(node.right, output, depth);
}
}
// Function to insert a new word in a Ternary Search Tree
fun insert(rootNode: TreeNode ? , word : String, position: Int): TreeNode ?
{
var node: TreeNode ? = rootNode;
if (rootNode == null)
{
node = TreeNode(word.get(position));
}
if (word.get(position) < node!!.data)
{
node.left = this.insert(node.left, word, position);
}
else if (word.get(position) > node.data)
{
node.right = this.insert(node.right, word, position);
}
else
{
if ((position + 1) < word.length)
{
node.equal = this.insert(node.equal, word, position + 1);
}
else
{
node.terminate = true;
}
}
return node;
}
// Handles the request of add new node
{
if (word.length == 0)
{
return;
}
this.root = this.insert(this.root, word, 0);
}
fun searchElement(node: TreeNode ? , word : String, position: Int): Boolean
{
if (node == null)
{
return false;
}
else if (word.get(position) < node.data)
{
return this.searchElement(node.left, word, position);
}
else if (word.get(position) > node.data)
{
return this.searchElement(node.right, word, position);
}
else
{
if (position + 1 < word.length)
{
// When word not empty
return this.searchElement(node.equal, word, position + 1);
}
else
{
// returns status to terminate word
return node.terminate;
}
}
}
// Handles the request of search word
fun searchTreeNode(word: String): Unit
{
print("\n Given : [" + word + "] \n");
if (word.length > 0 && this.searchElement(this.root, word, 0) == true)
{
print(" Found\n");
}
else
{
}
}
fun countSiblings(node: TreeNode ? ): Int
{
var count: Int = 0;
if (node?.left != null)
{
count += 1;
}
if (node?.right != null)
{
count += 1;
}
if (node?.equal != null)
{
count += 1;
}
return count;
}
fun deleteWord(node: TreeNode ? , word : String, position: Int): TreeNode ?
{
if (node == null)
{
// When delete node not exist
return null;
}
val child: Int = this.countSiblings(node);
if (word.get(position) < node.data)
{
node.left = this.deleteWord(node.left, word, position);
}
else if (word.get(position) > node.data)
{
node.right = this.deleteWord(node.right, word, position);
}
else
{
if ((position + 1) < word.length)
{
// When word not empty
node.equal = this.deleteWord(node.equal, word, position + 1);
}
else if (node.terminate == true)
{
if (child > 0)
{
// In case child node exist of deleted word
node.terminate = false;
}
else
{
return null;
}
}
}
if (child != this.countSiblings(node)
&& child == 1 && node.terminate == false)
{
// When need to remove node
return null;
}
return node;
}
}
fun main(args: Array < String > ): Unit
{
val tree: TernarySearchTree = TernarySearchTree();
print(" Ternary search tree\n");
tree.printWords(tree.root, "", 0);
// Case A
var word: String = "fee";
print("\n Delete word : " + word + " \n");
tree.root = tree.deleteWord(tree.root, word, 0);
print(" Ternary search tree\n");
tree.printWords(tree.root, "", 0);
// Case B
word = "code";
print("\n Delete word : " + word + " \n");
tree.root = tree.deleteWord(tree.root, word, 0);
print(" Ternary search tree\n");
tree.printWords(tree.root, "", 0);
// Case C
word = "milks";
print("\n Delete word : " + word + " \n");
tree.root = tree.deleteWord(tree.root, word, 0);
print(" Ternary search tree\n");
tree.printWords(tree.root, "", 0);
// Case D
word = "feel";
print("\n Delete word : " + word + " \n");
tree.root = tree.deleteWord(tree.root, word, 0);
print(" Ternary search tree\n");
tree.printWords(tree.root, "", 0);
}``````

#### input

`````` Ternary search tree
co
code
fee
feel
milk
run

Delete word : fee
Ternary search tree
co
code
feel
milk
run

Delete word : code
Ternary search tree
co
feel
milk
run

Delete word : milks
Ternary search tree
co
feel
milk
run

Delete word : feel
Ternary search tree
co
milk
run``````
``````package main
import "fmt"
/*
Go Program
Ternary Search Tree Deletion
*/
// Ternary search tree
type TreeNode struct {
data byte
terminate bool
left * TreeNode
equal * TreeNode
right * TreeNode
}
func getTreeNode(data byte) * TreeNode {
var me *TreeNode = &TreeNode {}
me.data = data
me.left = nil
me.right = nil
me.equal = nil
me.terminate = false
return me
}
type TernarySearchTree struct {
root * TreeNode
}
func getTernarySearchTree() * TernarySearchTree {
var me *TernarySearchTree = &TernarySearchTree {}
me.root = nil
return me
}
// Print the all words using recursion
func(this TernarySearchTree) printWords(node * TreeNode, output string, depth int) {
if node != nil {
// Visit left subtree
this.printWords(node.left, output, depth)
if node.terminate == true {
// Display word
fmt.Print(" ", (output + string(node.data)), "\n")
}
// Visit equal (middle) subtree
this.printWords(node.equal, output + string(node.data), depth + 1)
// Visit left subtree
this.printWords(node.right, output, depth)
}
}
// Function to insert a new word in a Ternary Search Tree
func(this TernarySearchTree) insert(rootNode * TreeNode, word string, position int) * TreeNode {
var node * TreeNode = rootNode
if rootNode == nil {
node = getTreeNode(word[position])
}
if word[position] < node.data {
node.left = this.insert(node.left, word, position)
} else if word[position] > node.data {
node.right = this.insert(node.right, word, position)
} else {
if (position + 1) < len(word) {
node.equal = this.insert(node.equal, word, position + 1)
} else {
node.terminate = true
}
}
return node
}
// Handles the request of add new node
if len(word) == 0 {
return
}
this.root = this.insert(this.root, word, 0)
}
func(this TernarySearchTree) searchElement(node * TreeNode, word string, position int) bool {
if node == nil {
return false
} else if word[position] < node.data {
return this.searchElement(node.left, word, position)
} else if word[position] > node.data {
return this.searchElement(node.right, word, position)
} else {
if position + 1 < len(word) {
// When word not empty
return this.searchElement(node.equal, word, position + 1)
} else {
// returns status to terminate word
return node.terminate
}
}
}
// Handles the request of search word
func(this TernarySearchTree) searchTreeNode(word string) {
fmt.Print("\n Given : [", word, "] \n")
if len(word) > 0 && this.searchElement(this.root, word, 0) == true {
fmt.Print(" Found\n")
} else {
}
}
func(this TernarySearchTree) countSiblings(node * TreeNode) int {
var count int = 0
if node.left != nil {
count++
}
if node.right != nil {
count++
}
if node.equal != nil {
count++
}
return count
}
func(this TernarySearchTree) deleteWord(node * TreeNode, word string, position int) * TreeNode {
if node == nil {
// When delete node not exist
return nil
}
var child int = this.countSiblings(node)
if word[position] < node.data {
node.left = this.deleteWord(node.left, word, position)
} else if word[position] > node.data {
node.right = this.deleteWord(node.right, word, position)
} else {
if (position + 1) < len(word) {
// When word not empty
node.equal = this.deleteWord(node.equal, word, position + 1)
} else if node.terminate == true {
if child > 0 {
// In case child node exist of deleted word
node.terminate = false
} else {
return nil
}
}
}
if child != this.countSiblings(node) && child == 1 && node.terminate == false {
// When need to remove node
return nil
}
return node
}
func main() {
var tree * TernarySearchTree = getTernarySearchTree()
fmt.Print(" Ternary search tree\n")
tree.printWords(tree.root, "", 0)
// Case A
var word string = "fee"
fmt.Print("\n Delete word : ", word, " \n")
tree.root = tree.deleteWord(tree.root, word, 0)
fmt.Print(" Ternary search tree\n")
tree.printWords(tree.root, "", 0)
// Case B
word = "code"
fmt.Print("\n Delete word : ", word, " \n")
tree.root = tree.deleteWord(tree.root, word, 0)
fmt.Print(" Ternary search tree\n")
tree.printWords(tree.root, "", 0)
// Case C
word = "milks"
fmt.Print("\n Delete word : ", word, " \n")
tree.root = tree.deleteWord(tree.root, word, 0)
fmt.Print(" Ternary search tree\n")
tree.printWords(tree.root, "", 0)
// Case D
word = "feel"
fmt.Print("\n Delete word : ", word, " \n")
tree.root = tree.deleteWord(tree.root, word, 0)
fmt.Print(" Ternary search tree\n")
tree.printWords(tree.root, "", 0)
}``````

#### input

`````` Ternary search tree
co
code
fee
feel
milk
run

Delete word : fee
Ternary search tree
co
code
feel
milk
run

Delete word : code
Ternary search tree
co
feel
milk
run

Delete word : milks
Ternary search tree
co
feel
milk
run

Delete word : feel
Ternary search tree
co
milk
run``````

## Time Complexity

The time complexity of the deletion operation in a Ternary Search Tree is dependent on the height of the tree and the structure of the tree itself. In the worst case, where the tree is skewed, the time complexity is O(N), where N is the number of nodes in the tree. However, in balanced TSTs, the time complexity can be better, approaching O(log N) on average.

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

Categories
Relative Post