Skip to main content

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:

  1. Create structures for TST nodes and the TST itself.
  2. Implement functions to create new TST nodes and a new TST.
  3. Define insertion logic to add words to the TST.
  4. Develop search logic to check if a word is present in the TST.
  5. Implement a function to traverse and print all words stored in the TST.
  6. 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.




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







Someone     521 Day ago
Very glad that you posted this solution!