Working with Java Trie, fails to identify word endings. Fails somewhere in recursion

Question

I am trying to create my own version of a Java Trie in order to have one, and to gain the knowledge it requires to make one, but this project has me perplexed. I have a very basic broken Trie here.

I am adding 3 words to the Trie (by using the first character of the word as the key, and the value being additional TrieNodes). If you notice, I have print statements inside the TrieNode class to check the values of isWord as the program runs. I want the last character in the word to have the isWord variable set to True. Thus identifying the end of a word (which I will later use to get the whole word).

When I first put the three words in, the output prints every letter of every word as they go into the Trie and correctly identifies which characters are word endings.

However, if IMMEDIATELY after entering words, I traverse the Trie and re-print all characters in the Trie and their isWord status, the 'e' in "Hello" is now suddenly identified as a word ending?

I have poured over this for hours and I just don't see why this is happening. Below is the working code:

package testcode;


import java.util.*;

public class TestCode {

    public static Trie t;
    public static void main (String[] args){
        t = new Trie();
        t.addWord("hello");
        t.addWord("hi");
        t.addWord("soup");
        //at this point the output correctly identifies word endings.
        t.findWords();
        /* but when iterating through the hash map it becomes evident that
        * when entering the word 'hi' the 'e' in 'hello' had its isWord variable
        * changed to true. I followed the logic and I do not see how or why this
        * is happening.
        */
    }
}

//This Trie class handles the root trie, and Trie commands.
class Trie{
    private TrieNode root;

    public Trie(){
        root = new TrieNode();
    }

    public void addWord(String word){
        root.addWord(word.toLowerCase());
    }

    public void findWords(){
        root.findWords();
    }
}

//Trie Node handles the nodes and words within the trie
class TrieNode{

    private TrieNode parent;
    private boolean isWord;
    private boolean hasChildren;
    private char character;
    private Map<Character, TrieNode> children = new HashMap<>();

    public TrieNode(){

        hasChildren = false;
        isWord = false;
    }

    public TrieNode(String word){

        this();
        addWord(word);

    }
    public void addWord(String word){

       char firstChar = word.charAt(0);


       if (children.get(firstChar) == null){

           if(word.length() > 1){

               hasChildren = true;
               children.put(firstChar, new TrieNode(word.substring(1)));
               children.get(firstChar).parent = this;
               System.out.print(firstChar + "--");
               System.out.println(isWord);
           }

           else{
               children.put(firstChar, new TrieNode());
               if(character == 'e'){
                   System.out.println("shits about to go down");
               }
               isWord = true;
               System.out.print(firstChar + "--");
               System.out.println(isWord);
           }
           children.get(firstChar).character = firstChar;
       }

       else {
           children.get(firstChar).addWord(word.substring(1));
       }
   }

    public void findWords(){
        for(Character key : children.keySet()){
            children.get(key).findWords();
            System.out.println(children.get(key).character + " -- " + isWord);     
      }
    }
}

This code generates the following output:

o--true
l--false
l--false
e--false
h--false
i--true
p--true
u--false
o--false
s--false
p -- true
u -- false
o -- false
s -- false
o -- true
l -- false
l -- false
e -- true    //notice the e here is now suddenly a word ending with isWord = true
i -- true
h -- false

Answer 1

There were a range of possible issues.. Parent/Child confusion, handling Leaf cases at the Parent Node, both in building & printout etc.

I note in your old 'findWords' code, you were printing child character but parent 'isWord' flag. Building the trie had undesirable divergence between "child node exist" and "create child node paths" -- such that 'isWord' could only be flagged on new paths, not existing paths. Building the trie also appeared to set 'isWord' on the parent rather than the leaf node.

In general, code that's a spaghetti of nested IF cases is highly likely to be unreliable. Code should be common where possible -- keep it in the main flow of the method, unless it really does belong inside the IF.

Here's clean & correct code:

class TrieNode{
    private TrieNode parent;
    private boolean isWord;
    private boolean hasChildren;
    private char character;
    private Map<Character, TrieNode> children = new HashMap<>();

    public TrieNode(){
        this.hasChildren = false;
        this.isWord = false;
    }
    public TrieNode (char ch) {
        this.character = ch;
        this.hasChildren = false;
        this.isWord = false;
    }

    public void addWord (String word){
        if (word.length() == 0) {
            this.isWord = true;
            System.out.println( character + " -- " + isWord);
            return;
        }

        // represent the Child Node;
        //       --
        char firstChar = word.charAt(0);
        TrieNode child = children.get( firstChar);
        if (child == null){
            child = new TrieNode( firstChar);
            children.put( firstChar, child);
            child.parent = this;
            hasChildren = true;
        }

        // add Remaining Word;
        //      -- call for 1-length words, as 0-length at Child sets 'IsWord'!
        child.addWord( word.substring(1));

        // print building here.
        System.out.println( character + " -- " + isWord);
    }



    public void findWords(){
        for(Character key : children.keySet()){
            children.get(key).findWords();
        }
        System.out.println( character + " -- " + isWord);     
    }
}