Trie Data Structure In Java - Implements Insert, Search and startswith operations

Let us assume, we are only implementing trie for lowercase english letters. And, there are 26 Lowercase English Letters. Having fixed our set of inputs, let us talk about the algorithm. Trie is a Tree datastructure. Where each node has a given number of children. In our case, the number of children are 26. Each Trie Node, contains a character, which is the value of the node and an array of children of Trie Node. Add a word

Root is set to root of Trie.
Iterate over each character in the word, one by one.
Check if the character node is present in the children array of current root
1. if it is not present, then create a New Trie Node with value set to current character.
2. update the root to point to newly created Trie Node
If character is present, then update the root to the Trie Node associated with current character
When we reach the end of iteration mark the root as The End Of Word or isWord. This signifies that, this is a word not just a prefix.

Search a Word

Root is set to root of trie.
Iterate over each character in the word, one by one.
Check if the character node is present in the children array, of current root.
1. If it is not present, then return false
2. If It is present,
  1. If we have reached end of word, then return true;
  2. Otherwise, update the root to point to current character Trie Node. And Continue Iteration.
If we have reached here, that means word was not found, so return false.

StartsWith a Prefix

Root is set to root of trie.
Iterate over each charactter of prefix, one by one.
Check if character is present in the children array of current root.
1. if not present then return false
2. if present check,
  1. if we have reached end of prefix, then return true
  2. Otherwise, update the root to point to current character Trie Node to continue iteration.
If we are here, that means the prefix was not found.

class Trie {

    private final char currentChar;
    private final Trie[] nextChars;
    private boolean isWord;

    public Trie() {
      this.currentChar = 'A';
      this.nextChars = new Trie[26];
      this.isWord = false;
    }

    private Trie(final char value, final boolean isWord){
      this.currentChar  = value;
      this.nextChars    = new Trie[26];
      this.isWord       = isWord;
    }
    
    public void insert(String word) {
        final int length = word.length();

        Trie root  = this;

        for(int index = 0; index < length; ++index) {
          final char ch = word.charAt(index);
          final int insertAt = ch - 'a';
          final Trie child = root.nextChars[insertAt];

          if(child == null){
            final Trie newTrieNode = new Trie(ch, (index + 1 == length));
            root.nextChars[insertAt] = newTrieNode;
            root = newTrieNode;
            continue;
          }

          root = child;
        }

        root.isWord = true;
    }
    
    public boolean search(String word) {
        final int length = word.length();
        Trie root = this;

        for(int index = 0; index < length; ++index) {
            final char ch = word.charAt(index);
            final int searchAt = ch - 'a';
            final Trie child = root.nextChars[searchAt];

            if(child == null) return false;
            if(index + 1 == length && child.isWord) return true;

            root = child;
        }
        
        return false;
    }
    
    public boolean startsWith(String prefix) {
        final int length = prefix.length();
        Trie root = this;

        for(int index = 0; index < length; ++index) {
            final char ch = prefix.charAt(index);
            final int searchAt = ch - 'a';
            final Trie child = root.nextChars[searchAt];
            
            if(child == null) return false;
            if(index + 1 == length) return true;

            root = child;
        }
        
        return false;
    }
}