Trie or Prefix Tree - All Operations

 Click Me
What is trie?
  • Trie is a search tree that is used to store and search strings in space and time-efficient way.
How String is stored in a trie?
  • A trie node consists of  Hashmap of <Character, address of next Trie Node> and a boolean flag endOfWord
  • In any trie node, we can store non-repetitive multiple characters.(Remember we use hashmap. Right?)
  • For any given string, it's each character is stored in different trie nodes.
  • After storing all the characters of a string in different trie nodes, we make a new trie node and mark its endOfWord flag as true, indicating the end of that particular string.
Practical Uses of Trie
  • Spelling checker
  • Autocomplete feature
Code (Please read comments in code for the explanation of each step)

import java.util.*;

// A node of trie
class TrieNode{
    
     // A hashmap to store the characters and address of its next trie node
    HashMap<Character,TrieNode> chars;
    
     // a boolean flag to indicate the end of the word
    boolean endOfWord;
    
    // creating a new TrieNode
    TrieNode(){
        this.chars = new HashMap<>();
        this.endOfWord = false;
    }
}

public class Main {
    
    // the root node of trie
    TrieNode root = new TrieNode();
    
    // function to insert a word into Trie
    // Time Complexity - O(n) , Space Complexity - O(n)
    public void insertWord(String word){
        
        // check if word is empty
        if(word.isEmpty()){
            System.out.println("Not able to insert into Trie, Word can't be empty");
            return;
        }
        
        // start from the root node of Trie
        TrieNode curr = root;
        
        // Check for each character, if it is present in current node  
        //if yes, go to next node
        // else make a new node, insert the current char into current node and point current node to nextNode
        // if last character is encountered, make endOfWord of nextNode as true
        for(int i=0;i<word.length();i++){
            Character ch = word.charAt(i);
            if(curr.chars.containsKey(ch)){
                // move current to next node
                curr = curr.chars.get(ch);
            }
            else{
                TrieNode nextNode = new TrieNode();
                curr.chars.put(ch,nextNode);
                curr = nextNode;
            }
            
            if(i==word.length()-1){
                curr.endOfWord = true;
            }
        }
        System.out.println("Successfully inserted: "+word+" in Trie");
    }
    
    
    // function to search a word in a trie
    // Time Complexity - 0(n),  Space Complexity - O(1)
    // Start with root node.
    // If the current char is in  current node, move to next node
    // if the current char is not in current node, return not found
    // if last char is reahced, check if the next node has endOfWord marked as true
    // If yes, return found, else return not found
    public void searchWord(String word){
        if(word.isEmpty()){
            System.out.println("Not able to search into Trie, Word can't be empty");
            return;
        }
        TrieNode curr = root;
        for(int i=0;i<word.length();i++){
            Character ch = word.charAt(i);
            // check if current node has current char
            if(!curr.chars.containsKey(ch)){
                System.out.println("Given word: "+word+" NOT FOUND in Trie");
                return;
            }
            else{
                // move to next node
                curr = curr.chars.get(ch);
            }
            
            // If last character node is reached
            if(i==word.length()-1 && curr.endOfWord==true){
                System.out.println("Given word: "+word+" FOUND in trie");
            }
            else if(i==word.length()-1 && curr.endOfWord==false){
                System.out.println("Given word: "+word+" NOT FOUND in Trie");
            }
        }
    }
    
    
    // function to delete a word from a Trie
    // Time Complexity - O(n) , Space Complexity - O(n)
    public void deleteWord(String word){
        if(word.isEmpty()){
            System.out.println("Not able to delete from Trie, Word can't be empty");
            return;
        }
        // set current node to root node
        TrieNode curr = root;
        
        // call overloaded method to delete as we will be using recursion to delete a word.
        // Reason to use recursion is that, in a Trie we always delete a word starting from bottom to up
        // Reason for bottom-up deletion is that a node of trie may be used for storing some other string too.
        // For example - bcde, bcdef and we want to delete bcde. But we also have nodes b,c,d,e also used to store string bcdef
        
        // An alternate to reursion here can be using stack explicitly and add nodes one by one from top to botton. 
        // Then pop stack till it is empty to ensure bottom-up deletion.
        
        //Recursion does this by using internal stack and it is easy to implement here . so I am going with recursive approach to delete a word.
        
        // First I will move to the endOfWord node recursively.
        // Remember, for each step we have to check if deleting this node will cause any problem ?
        // How to know if deleting a TrieNode will cause a problem ? 
        
        // 1. for endOfWord node of word to delete, if the node has more than 0 character, we can't delete that node.
        // 2. for other nodes except endOfWord of word to delete, we check if the current node has no. of characters gretaer than 1 (more chars including current char)
        //                                          if yes, we can't delete this node. We just remove this char from current node.
        // 3. also, for other nodes except endOfWord , we check if the currentnode's endOfWord is true. If yes, we can't delete this node.
        
        // KNOWING WHEN TO STOP DELETING IS VERY IMPORTANT.
        // So when to stop deleting ? 
        // If we find our first node which can't be deleted while moving bottom-up in recusrion, WE WILL STOP and then we will return curr node to subsequent recursive calls
        
        curr = deleteWord(curr,0,word);
        
        // if the root becomes null after deletion , we make a empty TrieNode and set it as new root.
        if(curr==null){
            root = new TrieNode();
        }
        
    }
    
    // Overloaded method to delete a word. This method is a recursive method.
    // After successfull completion it returns root node. 
    // If root node also gets deleted , it returns null
    
    // we will be passing current node , index -  to indicate current index of word and word to delete as parameters
    private TrieNode deleteWord(TrieNode curr, int index, String word){
        // this means when end of word node is reached
        if(index==word.length()){
            
            // if endOfWord node is reached and we get endOfWord as false, 
            // this means the given word is not present in Trie
            if(curr.endOfWord==false){
               System.out.println("Given word: "+word+" is not present in Trie, so can't delete it");
                return curr; 
            }
            
            // If word is present in trie
            else if(curr.endOfWord==true){
                // first we check if the endOfWord has 0 charcaters. That means safe to delete. 
                // If yes we return null its preceding recursive call.
                if(curr.chars.size()==0){
                    return null;
                }
                
                // if endOfWord has more than 0 chars, node is not safe to delete.
                // so we just mark endOfWord flag as false and return curr node which is endOfWord node to its preceding recursive call
                else{
                    curr.endOfWord = false;
                    return curr;
                }
            }
            
        }
        
        // IF endOfWord node is not reached yet
        
        // find the curr char
        Character ch = word.charAt(index); 
        
        // find the nextNode
        TrieNode nextNode = curr.chars.get(ch); 
        
        // if the nextnode is null and remember this is the case of not reaching endOfWord node yet.
        // hence this is the case where given word is not present in Trie
        if(nextNode==null){
            System.out.println("Given word: "+word+" is not present in Trie, so can't delete it");
            return curr; 
        }
        
        // Recursively moving to next node if nextnode is present
        nextNode = deleteWord(nextNode, index+1, word);
        
        // Updating the nextnode in currentnode.
        // the new nextNode's value will be coming from previous recursive call.
        curr.chars.put(ch,nextNode);
        
        
        // Remember the case where we talked about knowing when to stop deleting.
        // Here it is. If we don't get null value of nextNode from previous recursive call, that menas
        // the nextNode is not deleted, so we return currentnode as it is.
        
        // Receiving null in nextNode means, the nextNode was safe to delete and hence was deleted
        if(nextNode!=null){
            return curr;
        }
        
        // if we get nextNode as null, so iindicates nextNode was safe to delete. 
        // good, then let's check current node now. Because it is the nextNode of some node. Right?
        
        // if we find more than 1 character in current node or 
        // if we find currentnode's endOfWord flag as true, it means current node is being used and it is not safe to delete
        
        // we just remove the current char from current node and return currentnode as it is to the recursive function
        if(curr.chars.size()>1 || curr.endOfWord==true){
            curr.chars.remove(ch);
            return curr;
        }
        
        // when currentnode do not contains any other character except the character to delete and it's endOfWord is false,
        // it means it is not being used by any other word and it is safe to delete, so we just return null to the recursive call.
        else if(curr.chars.size()==1 && curr.endOfWord==false){
            return null;
        }
        
        else return curr;
        
    }
    

    public static void main(String[] args) throws Exception {
        Main trie = new Main();
        trie.insertWord("bcde");
        trie.insertWord("bckg");
        trie.insertWord("bcd");
        trie.insertWord("bcdef");
        trie.insertWord("bc");
        System.out.println();

        trie.searchWord("bc");
        trie.deleteWord("bc");
        trie.searchWord("bc");
        System.out.println();

        trie.searchWord("bcde");
        trie.deleteWord("bcde");
        trie.searchWord("bcde");
        System.out.println();

        trie.searchWord("bcd");
        System.out.println();
  
        trie.searchWord("bcdef");
        trie.deleteWord("bcdef");
        trie.searchWord("bcdef");
        System.out.println();
  
        trie.searchWord("bcd");
        trie.deleteWord("bcd");
        trie.searchWord("bcd");
        System.out.println();
  
        trie.searchWord("bckg");
        trie.deleteWord("bckg");
        trie.searchWord("bckg");
        System.out.println();
  
        trie.searchWord("b");
        trie.insertWord("b");
        trie.searchWord("b");
        trie.searchWord("bc");
        trie.insertWord("bc");
        trie.searchWord("bc");
        trie.searchWord("b");
        System.out.println();
        
        trie.searchWord("batman");
        trie.insertWord("batman");
        trie.searchWord("batman");
    
    }
}

Output:

Successfully inserted: bcde in Trie
Successfully inserted: bckg in Trie
Successfully inserted: bcd in Trie
Successfully inserted: bcdef in Trie
Successfully inserted: bc in Trie

Given word: bc FOUND in trie
Given word: bc NOT FOUND in Trie

Given word: bcde FOUND in trie
Given word: bcde NOT FOUND in Trie

Given word: bcd FOUND in trie

Given word: bcdef FOUND in trie
Given word: bcdef NOT FOUND in Trie

Given word: bcd FOUND in trie
Given word: bcd NOT FOUND in Trie

Given word: bckg FOUND in trie
Given word: bckg NOT FOUND in Trie

Given word: b NOT FOUND in Trie
Successfully inserted: b in Trie
Given word: b FOUND in trie
Given word: bc NOT FOUND in Trie
Successfully inserted: bc in Trie
Given word: bc FOUND in trie
Given word: b FOUND in trie

Given word: batman NOT FOUND in Trie
Successfully inserted: batman in Trie
Given word: batman FOUND in trie

Comments

Post a Comment

Popular posts from this blog

Binary Heap - Introduction

Image
#Image Credit - GeeksForGeeks Types of heap: Min Heap - every node is less than or equal to  its children(s) Max Heap - every node is more than or equal to its children(s) Operations on any heap : create insert extract/delete - we can extract/delete only the top node in any heap traverse delete entire heap get size of heap peek top of heap We should prefer implementing binary heap using arrays and not linked list, as during bottom to top heapify, in reaching the bottom rightmost node we take only 0(1) time in case of array but we take 0(n) time in case of linked list because first, we need to level order traverse the binary heap tree to get bottom-most rightmost element.  Heaps are used to efficiently implement:  Prim's Algorithm Heapsort Priority queue
Read more

Divide and Conquer - Introduction

Image
What is Divide and Conquer? Divide and Conquer is an algorithm paradigm in which we break down a given problem into smaller sub-problems of similar type until the sub-problems are small enough to be solved directly. The solution to these sub-problems are then combined to give a solution to the original problem.  Study the diagram below, it will then make more sense about what we do in Divide and Conquer : Where to Apply Divide and Conquer? The Divide and Conquer can be applied to all those problems that show Optimal Substructure property.  So, What is this Optimal Substructure property now? If we can break down a problem into similar sub-problems and the solution of these sub-problems can be used to create the solution of the whole problem, then that problem is said to have the Optimal Substructure property. For eg. : Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2),    In this example, we can see that if we want to find the Fibonacci number at the nth place, we can break this problem in
Read more

Bubble Sort

Time complexity - O(n^2)  || Space Complexity - O(1) Bubble sort is an inplace sorting algorithm, that means we do not any extra space while bubble sorting public class Main {     public static void main(String[] args) throws Exception {         int[] arr={1,4,4,5,6,2,3,90,120,43,0};                  System.out.println("UnSorted Array :");         for(int i=0;i<arr.length;i++){             System.out.print(arr[i]+" ");         }         System.out.println();         // bubble sort         for(int i=0;i<arr.length-1;i++){ // iterates through first to last cell             for(int j=0;j<arr.length-1-i;j++){ // inner loop controls swapping and extent to which swapping is to be performed in array                 if(arr[j]>arr[j+1]){                     int temp = arr[j];                     arr[j]=arr[j+1];                     arr[j+1]=temp;                 }             }             // after each iteration we ge
Read more