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)
	{
		printf(" Delete word not found \n");
		// 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();
	// Add word
	addNode(tree, "feel");
	addNode(tree, "fee");
	addNode(tree, "run");
	addNode(tree, "milk");
	addNode(tree, "co");
	addNode(tree, "code");
	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
 Delete word not found
 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
	public void addNode(String word)
	{
		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
		{
			System.out.print(" Not Found\n");
		}
	}
	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)
		{
			System.out.print(" Delete word not found \n");
			// 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();
		// Add words
		tree.addNode("feel");
		tree.addNode("fee");
		tree.addNode("run");
		tree.addNode("milk");
		tree.addNode("co");
		tree.addNode("code");
		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
 Delete word not found
 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
	public void addNode(String word)
	{
		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
		{
			Console.Write(" Not Found\n");
		}
	}
	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)
		{
			Console.Write(" Delete word not found \n");
			// 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();
		// Add words
		tree.addNode("feel");
		tree.addNode("fee");
		tree.addNode("run");
		tree.addNode("milk");
		tree.addNode("co");
		tree.addNode("code");
		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
 Delete word not found
 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
	void addNode(string word)
	{
		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
		{
			cout << " Not Found\n";
		}
	}
	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)
		{
			cout << " Delete word not found \n";
			// 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();
	// Add words
	tree->addNode("feel");
	tree->addNode("fee");
	tree->addNode("run");
	tree->addNode("milk");
	tree->addNode("co");
	tree->addNode("code");
	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
 Delete word not found
 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
	public	function addNode($word)
	{
		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
		{
			echo(" Not Found\n");
		}
	}
	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)
		{
			echo(" Delete word not found \n");
			// 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();
	// Add words
	$tree->addNode("feel");
	$tree->addNode("fee");
	$tree->addNode("run");
	$tree->addNode("milk");
	$tree->addNode("co");
	$tree->addNode("code");
	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
 Delete word not found
 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
	addNode(word)
	{
		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
		{
			process.stdout.write(" Not Found\n");
		}
	}
	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)
		{
			process.stdout.write(" Delete word not found \n");
			// 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();
	// Add words
	tree.addNode("feel");
	tree.addNode("fee");
	tree.addNode("run");
	tree.addNode("milk");
	tree.addNode("co");
	tree.addNode("code");
	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
 Delete word not found
 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
	def addNode(self, word) :
		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 :
			print(" Not Found")
		
	
	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) :
			print(" Delete word not found ")
			#  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()
	#  Add words
	tree.addNode("feel")
	tree.addNode("fee")
	tree.addNode("run")
	tree.addNode("milk")
	tree.addNode("co")
	tree.addNode("code")
	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
 Delete word not found
 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_reader :root
	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
	def addNode(word) 
		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
 
			print(" Not Found\n")
		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) 
			print(" Delete word not found \n")
			#  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()
	#  Add words
	tree.addNode("feel")
	tree.addNode("fee")
	tree.addNode("run")
	tree.addNode("milk")
	tree.addNode("co")
	tree.addNode("code")
	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 
 Delete word not found 
 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
		{
			print(" Not Found\n");
		}
	}
	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)
		{
			print(" Delete word not found \n");
			// 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();
		// Add words
		tree.addNode("feel");
		tree.addNode("fee");
		tree.addNode("run");
		tree.addNode("milk");
		tree.addNode("co");
		tree.addNode("code");
		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
 Delete word not found
 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
	fun addNode(word: String): Unit
	{
		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
		{
			print(" Not Found\n");
		}
	}
	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)
		{
			print(" Delete word not found \n");
			// 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();
	// Add words
	tree.addNode("feel");
	tree.addNode("fee");
	tree.addNode("run");
	tree.addNode("milk");
	tree.addNode("co");
	tree.addNode("code");
	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
 Delete word not found
 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
func(this *TernarySearchTree) addNode(word string) {
	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 {
		fmt.Print(" Not Found\n")
	}
}
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 {
		fmt.Print(" Delete word not found \n")
		// 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()
	// Add words
	tree.addNode("feel")
	tree.addNode("fee")
	tree.addNode("run")
	tree.addNode("milk")
	tree.addNode("co")
	tree.addNode("code")
	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
 Delete word not found
 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.

New Comment