Ternary Search Tree Insertion
A Ternary Search Tree (TST) is a type of data structure that combines the characteristics of both binary search trees and tries. It is used to store a dynamic set of strings in a way that allows for efficient insertion, deletion, and search operations. In a TST, each node has three branches: left, equal, and right, representing characters that are less than, equal to, or greater than the node's own character. This structure is particularly useful for tasks like autocomplete suggestions, spell checking, and searching for words with common prefixes.
Problem Statement
The problem is to implement insertion and search operations for a Ternary Search Tree. Given a set of words, we need to build a TST and perform searches to determine if specific words are present in the tree.
Example Scenario
Let's consider a set of words: "feel", "fee", "run", "milk", "co", and "code". We will construct a Ternary Search Tree using these words and demonstrate how insertion and search operations work.
Idea to Solve
To solve this problem, we'll follow these steps:
- Create structures for TST nodes and the TST itself.
- Implement functions to create new TST nodes and a new TST.
- Define insertion logic to add words to the TST.
- Develop search logic to check if a word is present in the TST.
- Implement a function to traverse and print all words stored in the TST.
- Demonstrate the insertion, search, and traversal operations using test cases.
Pseudocode
struct TreeNode:
char data
int terminate
TreeNode left
TreeNode equal
TreeNode right
struct TernarySearchTree:
TreeNode root
TernarySearchTree newTree():
tree = allocate memory for TernarySearchTree
tree.root = NULL
return tree
TreeNode newTreeNode(data):
node = allocate memory for TreeNode
node.data = data
node.left = NULL
node.equal = NULL
node.right = NULL
node.terminate = 0
return node
TreeNode insert(root, word):
if root is NULL:
node = newTreeNode(word[0])
root = node
if word[0] < root.data:
root.left = insert(root.left, word)
else if word[0] > root.data:
root.right = insert(root.right, word)
else:
if word[1] exists:
root.equal = insert(root.equal, word[1:])
else:
root.terminate = 1
return root
void traverseTST(root, output, depth):
if root is not NULL:
traverseTST(root.left, output, depth)
output[depth] = root.data
if root.terminate is true:
output[depth + 1] = '\0'
print output
traverseTST(root.equal, output, depth + 1)
traverseTST(root.right, output, depth)
int searchElement(root, word):
if root is NULL:
return 0
else if word[0] < root.data:
return searchElement(root.left, word)
else if word[0] > root.data:
return searchElement(root.right, word)
else:
if word[1] exists:
return searchElement(root.equal, word[1:])
else:
return root.terminate
void searchTreeNode(root, word):
print "Given:", word
if searchElement(root, word) is true:
print "Found"
else:
print "Not Found"
int main():
tree = newTree()
insert(tree.root, "feel")
insert(tree.root, "fee")
insert(tree.root, "run")
insert(tree.root, "milk")
insert(tree.root, "co")
insert(tree.root, "code")
print "Ternary search tree:"
traverseTST(tree.root, output, depth)
searchTreeNode(tree.root, "milk")
searchTreeNode(tree.root, "fee")
searchTreeNode(tree.root, "milks")
Code Solution
// C program for
// Ternary Search Tree Insertion
#include <stdio.h>
#include <stdlib.h>
// Ternary search tree
struct TreeNode
{
char data;
int terminate;
struct TreeNode *left;
struct TreeNode *equal;
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)
{
printf("Memory Overflow to create new tree node\n");
// Memory overflow
exit(0);
}
node->left = NULL;
node->equal = NULL;
node->right = NULL;
node->data = data;
node->terminate = 0;
return node;
}
// Print the all words using recursion
void printWords(struct TreeNode *root, char *output, int depth)
{
if (root != NULL)
{
// First traverse the left subtree
printWords(root->left, output, depth);
// Store the character of this node
output[depth] = root->data;
if (root->terminate)
{
// Include termination character
output[depth + 1] = '\0';
// Display word
printf(" %s\n", output);
}
// Visit equal (middle) subtree
printWords(root->equal, output, depth + 1);
// Visit left subtree
printWords(root->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;
}
}
// Handles the request of printing tree elements
void traverseTST(struct TreeNode *root)
{
if (root == NULL)
{
return;
}
// Find height of tree
int h = treeHeight(root) + 1;
// Use to collect word character
char output[h];
// Print all words
printWords(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->equal = insert(node->equal, 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 searchElement(struct TreeNode *root, char *word)
{
if (root == NULL)
{
return 0;
}
else if ( *word < root->data)
{
return searchElement(root->left, word);
}
else if ( *word > root->data)
{
return searchElement(root->right, word);
}
else
{
if ( *(word + 1))
{
// When word not empty
return searchElement(root->equal, word + 1);
}
else
{
// returns status to terminate word
return root->terminate;
}
}
}
// Handles the request of search word
void searchTreeNode(struct TreeNode *root, char *word)
{
printf("\n Given : [%s] \n", word);
if (searchElement(root, word) == 1)
{
printf(" Found\n");
}
else
{
printf(" Not Found\n");
}
}
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);
// Test Cases
searchTreeNode(tree->root, "milk");
searchTreeNode(tree->root, "fee");
searchTreeNode(tree->root, "milks");
return 0;
}
input
Ternary search tree
co
code
fee
feel
milk
run
Given : [milk]
Found
Given : [fee]
Found
Given : [milks]
Not Found
/*
Java Program
Ternary Search Tree Insertion
*/
// 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 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);
// Test Cases
tree.searchTreeNode("milk");
tree.searchTreeNode("fee");
tree.searchTreeNode("milks");
}
}
input
Ternary search tree
co
code
fee
feel
milk
run
Given : [milk]
Found
Given : [fee]
Found
Given : [milks]
Not Found
// Include header file
#include <iostream>
#include <string>
using namespace std;
/*
C++ Program
Ternary Search Tree Insertion
*/
// Ternary search tree
class TreeNode
{
public:
char data;
bool terminate;
TreeNode *left;
TreeNode *equal;
TreeNode *right;
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 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);
// Test Cases
tree->searchTreeNode("milk");
tree->searchTreeNode("fee");
tree->searchTreeNode("milks");
return 0;
}
input
Ternary search tree
co
code
fee
feel
milk
run
Given : [milk]
Found
Given : [fee]
Found
Given : [milks]
Not Found
// Include namespace system
using System;
/*
Csharp Program
Ternary Search Tree Insertion
*/
// 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 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);
// Test Cases
tree.searchTreeNode("milk");
tree.searchTreeNode("fee");
tree.searchTreeNode("milks");
}
}
input
Ternary search tree
co
code
fee
feel
milk
run
Given : [milk]
Found
Given : [fee]
Found
Given : [milks]
Not Found
<?php
/*
Php Program
Ternary Search Tree Insertion
*/
// 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");
}
}
}
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);
// Test Cases
$tree->searchTreeNode("milk");
$tree->searchTreeNode("fee");
$tree->searchTreeNode("milks");
}
main();
input
Ternary search tree
co
code
fee
feel
milk
run
Given : [milk]
Found
Given : [fee]
Found
Given : [milks]
Not Found
/*
Node JS Program
Ternary Search Tree Insertion
*/
// 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");
}
}
}
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);
// Test Cases
tree.searchTreeNode("milk");
tree.searchTreeNode("fee");
tree.searchTreeNode("milks");
}
main();
input
Ternary search tree
co
code
fee
feel
milk
run
Given : [milk]
Found
Given : [fee]
Found
Given : [milks]
Not Found
# Python 3 Program
# Ternary Search Tree Insertion
# 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 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)
# Test Cases
tree.searchTreeNode("milk")
tree.searchTreeNode("fee")
tree.searchTreeNode("milks")
if __name__ == "__main__": main()
input
Ternary search tree
co
code
fee
feel
milk
run
Given : [ milk ]
Found
Given : [ fee ]
Found
Given : [ milks ]
Not Found
# Ruby Program
# Ternary Search Tree Insertion
# 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
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)
# Test Cases
tree.searchTreeNode("milk")
tree.searchTreeNode("fee")
tree.searchTreeNode("milks")
end
main()
input
Ternary search tree
co
code
fee
feel
milk
run
Given : [milk]
Found
Given : [fee]
Found
Given : [milks]
Not Found
import scala.collection.mutable._;
/*
Scala Program
Ternary Search Tree Insertion
*/
// 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");
}
}
}
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);
// Test Cases
tree.searchTreeNode("milk");
tree.searchTreeNode("fee");
tree.searchTreeNode("milks");
}
}
input
Ternary search tree
co
code
fee
feel
milk
run
Given : [milk]
Found
Given : [fee]
Found
Given : [milks]
Not Found
/*
Kotlin Program
Ternary Search Tree Insertion
*/
// 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 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);
// Test Cases
tree.searchTreeNode("milk");
tree.searchTreeNode("fee");
tree.searchTreeNode("milks");
}
input
Ternary search tree
co
code
fee
feel
milk
run
Given : [milk]
Found
Given : [fee]
Found
Given : [milks]
Not Found
package main
import "fmt"
/*
Go Program
Ternary Search Tree Insertion
*/
// 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(int(node.data))), "\n")
}
// Visit equal (middle) subtree
this.printWords(node.equal, output + string(int(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 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)
// Test Cases
tree.searchTreeNode("milk")
tree.searchTreeNode("fee")
tree.searchTreeNode("milks")
}
input
Ternary search tree
co
code
fee
feel
milk
run
Given : [milk]
Found
Given : [fee]
Found
Given : [milks]
Not Found
Time Complexity
- Insertion: The time complexity of inserting a word in the TST depends on the height of the tree. In the worst case, it's O(h), where h is the height of the tree. However, on average, for a balanced TST, the insertion complexity is closer to O(log n), where n is the number of words in the TST.
- Search: Similar to insertion, the search time complexity is also O(h) in the worst case and O(log n) on average.
- Traversal: The traversal operation prints all words in lexicographical order, and thus, it takes O(n) time, where n is the number of words in the TST.
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