Trie in Java | Trie Program in Java

What is Trie?
Trie is a tree-like data structure used for efficient string storage and searching. It is also known as a prefix tree. Unlike a binary search tree, no node in the tree stores the key associated with that node, instead, its position in the tree defines the key with which it is associated. All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string. Values are normally not associated with every node, only with leaves and some inner nodes that correspond to keys of interest.

Trie Operations
Trie operations in Java typically include inserting a word into a Trie, searching for a word in a Trie, and removing a word from a Trie.

Insertion: This operation inserts a new string into the Trie. It starts from the root node and traverses down the Trie, creating new nodes as necessary. When it reaches the end of the string, it marks the last node as the end of a word.
Search: This operation checks if a given string exists in the Trie. It starts from the root node and traverses down the Trie, following the path that matches the characters of the string. If it reaches the end of the string and the last node is marked as the end of a word, it returns true.
Deletion: This operation removes a string from the Trie. It starts from the root node and traverses down the Trie, following the path that matches the characters of the string. When it reaches the end of the string, it marks the last node as not the end of a word. If a node has no children and is not the end of a word, it can be safely removed. If a node has children or is the end of a word, it cannot be removed.

Problem Description

Write a Java Program to implement Trie.

Program/Source Code

Here is the source code of the Java program to implement Trie. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

/*
 *  Java Program to Implement Trie
 */
 
import java.util.*;
 
class TrieNode 
{
    char content; 
    boolean isEnd; 
    int count;  
    LinkedList<TrieNode> childList; 
 
    /* Constructor */
    public TrieNode(char c)
    {
        childList = new LinkedList<TrieNode>();
        isEnd = false;
        content = c;
        count = 0;
    }  
    public TrieNode subNode(char c)
    {
        if (childList != null)
            for (TrieNode eachChild : childList)
                if (eachChild.content == c)
                    return eachChild;
        return null;
    }
}
 
class Trie
{
    private TrieNode root;
 
     /* Constructor */
    public Trie()
    {
        root = new TrieNode(' '); 
    }
     /* Function to insert word */
    public void insert(String word)
    {
        if (search(word) == true) 
            return;        
        TrieNode current = root; 
        for (char ch : word.toCharArray() )
        {
            TrieNode child = current.subNode(ch);
            if (child != null)
                current = child;
            else 
            {
                 current.childList.add(new TrieNode(ch));
                 current = current.subNode(ch);
            }
            current.count++;
        }
        current.isEnd = true;
    }
    /* Function to search for word */
    public boolean search(String word)
    {
        TrieNode current = root;  
        for (char ch : word.toCharArray() )
        {
            if (current.subNode(ch) == null)
                return false;
            else
                current = current.subNode(ch);
        }      
        if (current.isEnd == true) 
            return true;
        return false;
    }
    /* Function to remove a word */
    public void remove(String word)
    {
        if (search(word) == false)
        {
            System.out.println(word +" does not exist in trie\n");
            return;
        }             
        TrieNode current = root;
        for (char ch : word.toCharArray()) 
        { 
            TrieNode child = current.subNode(ch);
            if (child.count == 1) 
            {
                current.childList.remove(child);
                return;
            } 
            else 
            {
                child.count--;
                current = child;
            }
        }
        current.isEnd = false;
    }
}    
 
/* Class Trie Test */
public class TrieTest
{
    public static void main(String[] args)
    {            
        Scanner scan = new Scanner(System.in);
        /* Creating object of AATree */
        Trie t = new Trie(); 
        System.out.println("Trie Test\n");          
        char ch;
        /*  Perform tree operations  */
        do    
        {
            System.out.println("\nTrie Operations\n");
            System.out.println("1. insert ");
            System.out.println("2. delete");
            System.out.println("3. search");
            System.out.println("Enter your Choice:");                  
            int choice = scan.nextInt();            
            switch (choice)
            {
            case 1 : 
                System.out.println("Enter string element to insert");
                t.insert( scan.next() );                     
                break;                          
            case 2 : 
                System.out.println("Enter string element to delete");
                try
                {
                    t.remove( scan.next() ); 
                }                    
                catch (Exception e)
                {
                    System.out.println(e.getMessage()+" not found ");
                }
                break;                         
            case 3 : 
                System.out.println("Enter string element to search");
                System.out.println("Search result : "+ t.search( scan.next() ));
                break;                                          
            default : 
                System.out.println("Wrong Entry \n ");
                break;   
            }
 
            System.out.println("\nDo you want to continue (Type y or n) \n");
            ch = scan.next().charAt(0);                        
        } while (ch == 'Y'|| ch == 'y');               
    }
}

Program Explanation

1. This Java program implements a Trie data structure, which is used for efficient string searching and storage.
2. The program defines two classes, TrieNode and Trie, and a main class, TrieTest.
3. The TrieNode class represents a node in the Trie and stores a character, a count of how many times the character has been added, a boolean flag to indicate if it is the end of a word, and a linked list of child nodes.
4. The Trie class uses the TrieNode class to create a Trie, which has a root node initialized with a space character. It includes functions to insert a word into the Trie, search for a word in the Trie, and remove a word from the Trie.
5. The main class, TrieTest, provides a user interface to test the various Trie operations.
6. The program reads user input from the console to perform the various Trie operations until the user chooses to exit.

Program Output:

Trie Test
 
 
Trie Operations
 
1. insert
2. delete
3. search
1
Enter string element to insert
trie
 
Do you want to continue (Type y or n)
 
y
 
Trie Operations
 
1. insert
2. delete
3. search
Enter your Choice:
1
Enter string element to insert
tree
 
Do you want to continue (Type y or n)
 
y
 
Trie Operations
 
1. insert
2. delete
3. search
Enter your Choice:
1
Enter string element to insert
branch
 
Do you want to continue (Type y or n)
 
y
 
Trie Operations
 
1. insert
2. delete
3. search
Enter your Choice:
1
Enter string element to insert
beach
 
Do you want to continue (Type y or n)
 
y
 
Trie Operations
 
1. insert
2. delete
3. search
Enter your Choice:
3
Enter string element to search
bean
Search result : false
 
Do you want to continue (Type y or n)
 
y
 
Trie Operations
 
1. insert
2. delete
3. search
Enter your Choice:
3
Enter string element to search
beach
Search result : true
 
Do you want to continue (Type y or n)
 
y
 
Trie Operations
 
1. insert
2. delete
3. search
Enter your Choice:
2
Enter string element to delete
bean
bean does not exist in trie
 
 
Do you want to continue (Type y or n)
 
y
 
Trie Operations
 
1. insert
2. delete
3. search
Enter your Choice:
2
Enter string element to delete
beach
 
Do you want to continue (Type y or n)
 
y
 
Trie Operations
 
1. insert
2. delete
3. search
Enter your Choice:
3
Enter string element to search
beach
Search result : false
 
Do you want to continue (Type y or n)
 
y
 
Trie Operations
 
1. insert
2. delete
3. search
Enter your Choice:
2
Enter string element to delete
tree
 
Do you want to continue (Type y or n)
 
y
 
Trie Operations
 
1. insert
2. delete
3. search
Enter your Choice:
3
Enter string element to search
tree
Search result : false
 
Do you want to continue (Type y or n)
 
y
 
Trie Operations
 
1. insert
2. delete
3. search
Enter your Choice:
3
Enter string element to search
trie
Search result : true
 
Do you want to continue (Type y or n)
 
y
 
Trie Operations
 
1. insert
2. delete
3. search
Enter your Choice:
2
Enter string element to delete
trie
 
Do you want to continue (Type y or n)
 
y
 
Trie Operations
 
1. insert
2. delete
3. search
Enter your Choice:
3
Enter string element to search
trie
Search result : false
 
Do you want to continue (Type y or n)
 
n

To practice programs on every topic in Java, please visit “Programming Examples in Java”, “Data Structures in Java” and “Algorithms in Java”.

If you find any mistake above, kindly email to [email protected]

« Prev - Java Program to Implement Treap

» Next - Java Program to Evaluate an Expression using Stacks

Related Posts:

Recommended Articles: