Autocomplete using Tries

Question

import java.util.ArrayList;


public class AutoComplete {
    boolean newWord = false;
    ArrayList<String> all = new ArrayList<String>();

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

    void add(String s){
        TrieNode temp = root;
//      TrieNode parent = root;

        for(int i=0; i < s.length(); i++){
            int t = s.charAt(i);
            t = t - 97;
            while((temp.links[t]) != null && i < s.length()-1){

                temp = temp.links[t];
                t = s.charAt(++i);
                t = t - 97;

//              parent = temp;
            }
            if( i != s.length()-1){
                temp.links[t] = new TrieNode((char)(97+t), false, null);
//              parent = temp.links[t];
            }
            else{
                temp.links[t] = new TrieNode((char) (97+t), true, null);
//              parent = temp.links[t];         
            }
            temp = temp.links[t];
        }
    }

    void readTree(String find){
        int len = find.length();
        int i = 0;
        TrieNode temp = root;
        String match = "";
        while(i != len){
            int t = find.charAt(i);
            t = t - 97;
            temp = temp.links[t];
            if(temp == null)
                break;
            match = match + temp.letter;
            i++;
        }
        if(match.length() > 0)
            match = match.substring(0,match.length()-1);
        printAll(temp, match);
    }

    void printAll(TrieNode t, String parent){
        if(t== null)
            return;
        parent = parent + t.letter;
        if(t.fullWord){
            System.out.println(parent);
        }
        for(int i = 0; i < 26; i++){
            printAll(t.links[i], parent);
        }
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        AutoComplete a = new AutoComplete();

        a.add("tea");
        a.add("team");
        a.add("teach");
        a.add("teacher");
        a.readTree("t");
    }

}

I am trying to implement autocomplete using tries, it works fine when the elements in the trie are added from lower length to higher length

if I add elements in this order

a.add("tea");
a.add("team");
a.add("teach");
a.add("teacher");

I get following output for a.readTree("t");

tea
teach
teacher
team

but if I add elements in this order

a.add("teacher");
a.add("teach");
a.add("team");
a.add("tea");

I get following output for a.readTree("t");

tea

Final Working solution

public class AutoComplete {
    void add(String s, TrieNode root){
        //To keep the root node intact
        TrieNode temp = root;

        //Iterate through each char in string s
        for(int i=0; i < s.length(); i++){
            //each character in string
            int t = s.charAt(i);
            //its corresponding value in array links 
            t = t - 'a';
            //if some part of string is already present in array then just loop through it except th
            while((temp.links[t]) != null && i < s.length()-1){
                //increment i since first char is present
                i = i +1;
                //increment in trie
                temp = temp.links[t];
                //go to next char in string and 
                //go to that char location in array
                t = s.charAt(i)- 'a';
            }
            //Add only till before the last character
            if( i < s.length()-1){
                temp.links[t] = new TrieNode((char)('a'+t), false);
            }
            //for last character of string
            else{
                // if last character is not present
                if(temp.links[t] == null){
                    temp.links[t] = new TrieNode((char) ('a'+t), true);                 
                }
                // if last character already exist
                else{
                    temp.links[t].fullWord = true;
                }
            }
            //increment the trie
            temp = temp.links[t];
        }
    }
    void readTree(String find, TrieNode root){
        //get length in len
        int len = find.length();
        int i = 0;
        TrieNode temp = root;
        //initialize string to store the result
        String match = "";
        while(i < len){
            //get first char of search string
            int t = find.charAt(i) - 'a';
            //go to its array location
            temp = temp.links[t];
            //location is null then break else continue
            if(temp == null)
                break;
            //keep appending the found char and increment the index
            match = match + temp.letter;
            i++;
        }
        //if suggestions exist
        if(match.length() > 0)
            //pass the match string except for the last element
            match = match.substring(0,match.length()-1);
        printAll(temp, match);
    }

    void printAll(TrieNode t, String parent){
        if(t== null)
            return;
        parent = parent + t.letter;
        if(t.fullWord){
            System.out.println(parent);
        }
        for(int i = 0; i < 26; i++){
            printAll(t.links[i], parent);
        }
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        TrieNode root = new TrieNode('!', false);
        AutoComplete a = new AutoComplete();

        a.add("tea", root);
        a.add("team", root);
        a.add("teach", root);
        a.add("teacher", root);
        a.readTree("t", root);
    }

}

Answer 1

The problem is here:

else{ //i == s.length - 1
        temp.links[t] = new TrieNode((char) (97+t), true, null);      
    }

When you add "teach", it will new a node at char 'h', which replace the node 'h' of teacher. You should write it like this:

else{ //i == s.length - 1
        if(temp.links[t] == null) {
            temp.links[t] = new TrieNode((char) (97+t), true, null);    
        } 
        else {
            // change the leaf tag from false to true 
        }
    }

Answer 2

The concept of a Trie seems poorly captured in your code. It is fairly hard to discern all the possible cases of your for and your while loops and still remain readable. In "make it run, make it right, make it fast" manner you should keep your first implementation as simple as possible.

Given that the order of adding strings to your Trie does affect your query result your code obviously does not run yet. To keep it as simple as possible you should only need to look at the first character of your newly added string and act according to wether you find it in your root and use recursion after that. This might blow your runtime, but that will only be your third concern (after making it right). Too many changes to put in an answer though if you do not show us how you would like to implement TrieNode.