Trie Data Structure( or Prefix tree) Java Implementation

Trie Java Implementation

Also know as Prefix Tree.
Below is the  basic Java implementation of Trie Data Structure.We can search the the word in Trie in O(n) complexity.

Below is the implementation of Trie in Java:

import java.util.HashMap;


class Test {

TrieNode root;

    static class TrieNode{
        HashMap<Character, TrieNode> map;
        boolean isWord;
     
        TrieNode(){
        map = new HashMap<Character, TrieNode>();
        }
     
    }
 
 
    /** Initialize your data structure here. */
    public Test() {
    root = new TrieNode();
    }
 
    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode currentNode = root;
        int i=0;
        for(char ch:word.toCharArray()){
        i++;
            if(!currentNode.map.containsKey(ch)){
                currentNode.map.put(ch, new TrieNode());
            }
            currentNode = currentNode.map.get(ch);
            if(i==word.length()) {
            currentNode.isWord = true;
            }
        }
    }
 
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
    TrieNode currentNode = root;
        for(char ch:word.toCharArray()){
            if(!currentNode.map.containsKey(ch)){
                return false;
            }
            currentNode = currentNode.map.get(ch);
        }
        return currentNode.isWord;
    }
 
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
    TrieNode currentNode = root;
        for(char ch:prefix.toCharArray()){
            if(!currentNode.map.containsKey(ch)){
                return false;
            }
            currentNode = currentNode.map.get(ch);
        }
        return true;
    }
 
    public static void main(String...ar) {
    Test ob = new Test();
    ob.insert("Hello");
    ob.insert("HelGo");
    System.out.println(ob.startsWith("H"));
    System.out.println(ob.search("Hello"));
    System.out.println(ob.startsWith("Hel"));
    System.out.println(ob.search("GG"));
    }
}