Longest word in ternary search tree

0 0 9 minutes read

Given a set of words represented in a ternary search tree, find the length of largest word among them.

Examples:

Input : {"Prakriti", "Raghav", 
           "Rashi", "Sunidhi"}
Output : Length of largest word in 
         ternary search tree is: 8

Input : {"Boats", "Boat", "But", "Best"}
Output : Length of largest word in 
         ternary search tree is: 5

Prerequisite : Ternary Search Tree
The idea is to recursively search the max of left subtree, right subtree and equal tree.
If the current character is same as the root’s character increment with 1.

Implementation:

C++

// C++ program to find the length of largest word
// in ternary search tree
#include <iostream>
#include <cstring>
#define MAX 50
 
using namespace std;
 
// A node of ternary search tree
struct Node
{
    char data;
 
    // True if this character is last
    // character of one of the words
    unsigned isEndOfString : 1;
 
    Node *left, *eq, *right;
 
    // A utility function to create a new
    // ternary search tree node
    Node(char data)
    {
        this->data = data;
        this->isEndOfString = 0;
        this->left = this->eq = this->right = nullptr;
    }
};
 
// Function to insert a new word in a Ternary
// Search Tree
void insert(Node** root, const char* word)
{
    // Base Case: Tree is empty
    if (!(*root))
        *root = new Node(*word);
 
    // If current character of word is smaller
    // than root's character, then insert this
    // word in left subtree of root
    if (*word < (*root)->data)
        insert(&((*root)->left), word);
 
    // If current character of word is greater
    // than root's character, then insert this
    // word in right subtree of root
    else if (*word > (*root)->data)
        insert(&((*root)->right), word);
 
    // If current character of word is same as
    // root's character,
    else
    {
        if (*(word + 1))
            insert(&((*root)->eq), word + 1);
 
        // the last character of the word
        else
            (*root)->isEndOfString = 1;
    }
}
 
// Function to find max of three numbers
int max(int a, int b, int c)
{
    int max;
    if (a >= b && a >= c)
        max = a;
    else if (b >= a && b >= c)
        max = b;
    else
        max = c;
     
    return max;
}
 
// Function to find length of largest word in TST
int maxLengthTST(Node* root)
{
    if (root == nullptr)
        return 0;
    return max(maxLengthTST(root->left),
        maxLengthTST(root->eq) + 1,
        maxLengthTST(root->right));
}
 
// Driver program to test above functions
int main()
{
    Node* root = nullptr;
    insert(&root, "Prakriti");
    insert(&root, "Raghav");
    insert(&root, "Rashi");
    insert(&root, "Sunidhi");
    int value = maxLengthTST(root);
    cout << "Length of largest word in ternary search tree is: " << value << endl;
 
    return 0;
}
 
// This code is contributed by Vaibhav

C

// C program to find the length of largest word 
// in ternary search tree
#include <stdio.h>
#include <stdlib.h>
#define MAX 50
  
// A node of ternary search tree
struct Node
{
    char data;
  
    // True if this character is last 
   // character of one of the words
    unsigned isEndOfString: 1;
  
    struct Node *left, *eq, *right;
};
  
// A utility function to create a new 
// ternary search tree node
struct Node* newNode(char data)
{
    struct Node* temp = 
     (struct Node*) malloc(sizeof( struct Node ));
    temp->data = data;
    temp->isEndOfString = 0;
    temp->left = temp->eq = temp->right = NULL;
    return temp;
}
  
// Function to insert a new word in a Ternary 
// Search Tree
void insert(struct Node** root, char *word)
{
    // Base Case: Tree is empty
    if (!(*root))
        *root = newNode(*word);
  
    // If current character of word is smaller
    // than root's character, then insert this 
    // word in left subtree of root
    if ((*word) < (*root)->data)
        insert(&( (*root)->left ), word);
  
    // If current character of word is greater
    // than root's character, then insert this
    // word in right subtree of root
    else if ((*word) > (*root)->data)
        insert(&( (*root)->right ), word);
  
    // If current character of word is same as
    // root's character,
    else
    {
        if (*(word+1))
            insert(&( (*root)->eq ), word+1);
  
        // the last character of the word
        else
            (*root)->isEndOfString = 1;
    }
}
 
 
// Function to find max of three numbers
int max(int a, int b, int c)
{
    int max;
    if (a >= b && a >= c)
        max = a;
    else if (b >= a && b >= c)
        max = b;
    else
        max = c;
}
 
// Function to find length of largest word in TST
int maxLengthTST(struct Node *root)
{
    if (root == NULL)
        return 0;
    return max(maxLengthTST(root->left), 
               maxLengthTST(root->eq)+1, 
               maxLengthTST(root->right));
}
 
// Driver program to test above functions
int main()
{
    struct Node *root = NULL; 
    insert(&root, "Prakriti");
    insert(&root, "Raghav");
    insert(&root, "Rashi");
    insert(&root, "Sunidhi");
    int value = maxLengthTST(root);
    printf("Length of largest word in "
    "ternary search tree is: %d\n", value);
  
    return 0;
}

Java

// Java program to find the length of largest word 
// in ternary search tree
public class GFG {
 
    static final int MAX = 50;
       
    // A node of ternary search tree
    static class Node
    {
        char data;
       
        // True if this character is last 
        // character of one of the words
        int isEndOfString = 1;
       
        Node left, eq, right;
         
        // constructor
        Node(char data)
        {
            this.data = data;
            isEndOfString = 0;
            left = null;
            eq = null;
            right = null;
        }
    }
     
    // Function to insert a new word in a Ternary 
    // Search Tree
    static Node insert(Node root, String word, int i)
    {
        // Base Case: Tree is empty
        if (root == null)
            root = new Node(word.charAt(i));
       
        // If current character of word is smaller
        // than root's character, then insert this 
        // word in left subtree of root
        if (word.charAt(i) < root.data)
            root.left = insert(root.left, word, i);
       
        // If current character of word is greater
        // than root's character, then insert this
        // word in right subtree of root
        else if (word.charAt(i) > root.data)
            root.right = insert(root.right, word, i);
       
        // If current character of word is same as
        // root's character,
        else
        {
            if (i + 1 < word.length())
                root.eq = insert(root.eq, word, i + 1);
       
            // the last character of the word
            else
                root.isEndOfString = 1;
        }
        return root;
    }
      
      
    // Function to find max of three numbers
    static int max(int a, int b, int c)
    {
        int max;
        if (a >= b && a >= c)
            max = a;
        else if (b >= a && b >= c)
            max = b;
        else
            max = c;
        return max;
    }
      
    // Function to find length of largest word in TST
    static int maxLengthTST(Node root)
    {
        if (root == null)
            return 0;
        return max(maxLengthTST(root.left), 
                   maxLengthTST(root.eq)+1, 
                   maxLengthTST(root.right));
    }
      
    // Driver program to test above functions
    public static void main(String args[])
    {
        Node root = null; 
        root = insert(root, "Prakriti", 0);
        root = insert(root, "Raghav",  0);
        root = insert(root, "Rashi", 0);
        root = insert(root, "Sunidhi", 0);
        int value = maxLengthTST(root);
        System.out.println("Length of largest word in "+
        "ternary search tree is: "+ value);
    }
}
// This code is contributed by Sumit Ghosh

Python3

MAX = 50
 
class Node:
 
    def __init__(self,data):
        self.left = None
        self.right = None
        self.data = data
        self.isEndOfString = 0
        self.eq = None
     
# Function to insert a word in a Ternary
# Search Tree
def insert(root, word, i):
     
    # Base Case: Tree is empty
    if (root == None):
        root = Node(word[i])
         
    # If current character of word is smaller
    # than root's character, then insert self
    # word in left subtree of root
    if (word[i] < root.data):
        root.left = insert(root.left, word, i)
 
    # If current character of word is greater
    # than root's character, then insert self
    # word in right subtree of root
    elif (word[i] > root.data):
        root.right = insert(root.right, word, i)
         
    # If current character of word is same as
    # root's character,
    else:
        if (i + 1 < len(word)):
            root.eq = insert(root.eq, word, i + 1)
         
        # the last character of the word
        else:
            root.isEndOfString = 1
    return root
         
         
# Function to find max of three numbers
def max(a, b, c):
 
    if (a >= b and a >= c):
        Max = a
    elif (b >= a and b >= c):
        Max = b
    else:
        Max = c
    return Max
         
# Function to find length of largest word in TST
def maxLengthTST(root):
 
    if (root == None):
            return 0
    return max(maxLengthTST(root.left),
                maxLengthTST(root.eq)+1,
                maxLengthTST(root.right))
     
root = None
root = insert(root, "Prakriti", 0)
root = insert(root, "Raghav", 0)
root = insert(root, "Rashi", 0)
root = insert(root, "Sunidhi", 0)
value = maxLengthTST(root)
print("Length of largest word in ternary search tree is: "+ str(value))
 
# This code is contributed by shinjanpatra

C#

// C# program to find the length of largest word 
// in ternary search tree 
using System;
 
class GFG 
{
 
    static readonly int MAX = 50;
         
    // A node of ternary search tree
    public class Node
    {
        public char data;
         
        // True if this character is last 
        // character of one of the words
        public int isEndOfString = 1;
         
        public Node left, eq, right;
         
        // constructor
        public Node(char data)
        {
            this.data = data;
            isEndOfString = 0;
            left = null;
            eq = null;
            right = null;
        }
    }
     
    // Function to insert a new word in a Ternary 
    // Search Tree
    static Node insert(Node root, String word, int i)
    {
        // Base Case: Tree is empty
        if (root == null)
            root = new Node(word[i]);
         
        // If current character of word is smaller
        // than root's character, then insert this 
        // word in left subtree of root
        if (word[i] < root.data)
            root.left = insert(root.left, word, i);
         
        // If current character of word is greater
        // than root's character, then insert this
        // word in right subtree of root
        else if (word[i] > root.data)
            root.right = insert(root.right, word, i);
         
        // If current character of word is same as
        // root's character,
        else
        {
            if (i + 1 < word.Length)
                root.eq = insert(root.eq, word, i + 1);
         
            // the last character of the word
            else
                root.isEndOfString = 1;
        }
        return root;
    }
     
     
    // Function to find max of three numbers
    static int max(int a, int b, int c)
    {
        int max;
        if (a >= b && a >= c)
            max = a;
        else if (b >= a && b >= c)
            max = b;
        else
            max = c;
        return max;
    }
     
    // Function to find length of largest word in TST
    static int maxLengthTST(Node root)
    {
        if (root == null)
            return 0;
        return max(maxLengthTST(root.left), 
                maxLengthTST(root.eq) + 1, 
                maxLengthTST(root.right));
    }
     
    // Driver code
    public static void Main()
    {
        Node root = null; 
        root = insert(root, "Prakriti", 0);
        root = insert(root, "Raghav", 0);
        root = insert(root, "Rashi", 0);
        root = insert(root, "Sunidhi", 0);
        int value = maxLengthTST(root);
        Console.WriteLine("Length of largest word in "+
        "ternary search tree is: "+ value);
    }
}
 
/* This code contributed by PrinciRaj1992 */

Javascript

<script>
    // Javascript program to find the length of largest word 
    // in ternary search tree
    let MAX = 50;
     
    class Node
    {
        constructor(data) {
           this.left = null;
           this.right = null;
           this.data = data;
           this.isEndOfString = 0;
           this.eq = null;
        }
    }
     
    // Function to insert a new word in a Ternary 
    // Search Tree
    function insert(root, word, i)
    {
        // Base Case: Tree is empty
        if (root == null)
            root = new Node(word[i]);
         
        // If current character of word is smaller
        // than root's character, then insert this 
        // word in left subtree of root
        if (word[i] < root.data)
            root.left = insert(root.left, word, i);
         
        // If current character of word is greater
        // than root's character, then insert this
        // word in right subtree of root
        else if (word[i] > root.data)
            root.right = insert(root.right, word, i);
         
        // If current character of word is same as
        // root's character,
        else
        {
            if (i + 1 < word.length)
                root.eq = insert(root.eq, word, i + 1);
         
            // the last character of the word
            else
                root.isEndOfString = 1;
        }
        return root;
    }
        
        
    // Function to find max of three numbers
    function max(a, b, c)
    {
        let Max;
        if (a >= b && a >= c)
            Max = a;
        else if (b >= a && b >= c)
            Max = b;
        else
            Max = c;
        return Max;
    }
        
    // Function to find length of largest word in TST
    function maxLengthTST(root)
    {
        if (root == null)
            return 0;
        return max(maxLengthTST(root.left), 
                   maxLengthTST(root.eq)+1, 
                   maxLengthTST(root.right));
    }
     
    let root = null; 
    root = insert(root, "Prakriti", 0);
    root = insert(root, "Raghav",  0);
    root = insert(root, "Rashi", 0);
    root = insert(root, "Sunidhi", 0);
    let value = maxLengthTST(root);
    document.write("Length of largest word in "+
                       "ternary search tree is: "+ value);
 
// This code is contributed by divyeshrabadiya07.
</script>

Output

Length of largest word in ternary search tree is: 8

If you like zambiatek and would like to contribute, you can also write an article using write.zambiatek.com or mail your article to review-team@zambiatek.com. See your article appearing on the zambiatek main page and help other Geeks.

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!