Auto complete in Tries, trouble printing root nodes

Question

Here in this Trie, I'm trying to implement auto complete feature, I'm sure inserting into the trie is correct, but while trying to print im unable to print first letter of each word, because, while back tracking it is not printing the parent node, i somehow have to print the parent node, for doing that i have added parent_letter to the node, but at certain cases it is failing.

For example: These are the words in the Trie :

dehradun
delhi
dhanbad
dhule
dibrugarh
dimapur
dindigul
durgapur

If i pass the letter 'd'.

I get :

dehradun
elhi
dhanbad
hule
dibrugarh
imapur
indigul
durgapur

Source Code :

class TrieNode {
    char letter; // to store the letter
    TrieNode[] links; // array of 26 Nodes
    boolean fullword; // check for word
    public TrieNode parent; // storing parent letter

    TrieNode(char letter, boolean fullword, TrieNode p) {
        this.letter = letter;
        links = new TrieNode[26];
        this.fullword = fullword;
        this.parent = p;

    }
}

class temp8 {
    boolean new_word = false;
    ArrayList<String> al = new ArrayList<String>();

    TrieNode root = new TrieNode('!', false, null);

    void construct_trie(String s) {
        TrieNode temp = root; // copy root node
        TrieNode check;
        TrieNode par = root; // initially parent is root

        for (int i = 0; i < s.length(); i++) // loop over each character in word
        {
            int t = s.charAt(i); // integer value of character

            t = t - 97; // calculate appropriate index for array

            while ((check = temp.links[t]) != null) // check if root is null..
            {
                temp = temp.links[t]; // go forward
                t = s.charAt(++i);
                t = t - 97;
                par = temp; // update parent
            }

            if (i != s.length() - 1) // if not end of word..pass false
            {
                temp.links[t] = new TrieNode((char) (t + 97), false, par);
                par = temp.links[t];
            } else // if end of word..pass true to full word
            {
                temp.links[t] = new TrieNode((char) (t + 97), true, par);
                par = temp.links[t];
            }

            temp = temp.links[t]; // update temp..

        }
    }

    void read_trie(String find) // pass the intial string
    {
        int len = find.length();
        int i = 0;

        TrieNode temp = root; // copy root

        while (i != len) // go until the string matches
        {
            int t = find.charAt(i);
            t = t - 97;

            temp = temp.links[t];

            i++;

        }

        print_all(temp); // pass the node

    }

    void print_all(TrieNode t) // from here we have to recursively print all
                                // nodes if they are not null
    {

        if (t == null) // base condition
        {
            return;
        }

        if (new_word) // initially for first time don't print parent letter
        {
            System.out.print(t.parent.letter);
            new_word = false;
        }

        System.out.print(t.letter);

        if (t.fullword) {
            System.out.println();
            new_word = true;
        }

        for (int i = 0; i < 26; i++) {
            print_all(t.links[i]);

        }
    }
}

Answer 1

Your parent's letter is only being printed once per branch off of the root; it's better to just pass the parent's string to the child and only print when you reach a full word.

read code:

    void read_trie(String find) // pass the intial string
    {
        int len = find.length();
        int i = 0;

        TrieNode temp = root; // copy root

        String match = "";
        while (i != len) // go until the string matches
        {
            int t = find.charAt(i);
            t = t - 97;

            temp = temp.links[t];
            if (temp==null) break;
            match += temp.letter;

            i++;
        }

        // Remove the last letter since it's added in the print code below
        if (match.length()>0) match = match.substring(0, match.length()-1);
        print_all(temp, match); // pass the node
    }

print code:

    void print_all(TrieNode t, String parent) 
            // from here we have to recursively print all nodes if they are not null
    {
        if (t == null) // base condition
        {
            return;
        }

        parent += t.letter; // prepend parent to child
        if (t.fullword) {
                // only print when you reach a full word
            System.out.println(parent);
        }

        for (int i = 0; i < 26; i++) {
                // recurse into each child, prepending the parent's string
            print_all(t.links[i],parent);
        }
    }