LongestWord.java

package Tries;

public class LongestWord {
    static class Node {
        Node[] children = new Node[26];
        boolean endOfWord = false;

        Node() {
            for (int i = 0; i < 26; i++) {
                // by default these are null values
                children[i] = null;
            }
        }
    }
    // declaring empty Root node
    public static Node root = new Node();

    // Insert into trie
    public static void insert(String word){ //O[L]
        Node curr = root;
        for (int level = 0; level <word.length(); level++){
            int index = word.charAt(level) - 'a';
            if (curr.children[index] == null){
                // create node : if does not exist
                curr.children[index] = new Node();
            }
            curr = curr.children[index];
        }
        curr.endOfWord = true;
    }

    // Search into trie
    public static boolean search(String key){
        Node curr = root;
        for (int level=0; level<key.length(); level++){
            int index = key.charAt(level) - 'a';
            if (curr.children[index] == null){
//                    last condition
                return false;
            }
            curr = curr.children[index];
        }
        if (curr.endOfWord == true) return true;
        else return false;
    }

    public static String ans = "";
    public static void longestWord(Node root, StringBuilder tmp){
        if (root == null) {
            return;
        }

        for (int i=0; i<26; i++){
            if (root.children[i] != null && root.children[i].endOfWord == true){
                char ch = (char)(i +'a');
                tmp.append(ch);
                if (tmp.length() > ans.length()) {
                    ans = tmp.toString();
                }
                longestWord(root.children[i], tmp);
                //backtrack
                tmp.deleteCharAt(tmp.length()-1);
            }
        }
    }

    public static void main(String[] args) {
        String[] words = {"a","banana", "ap", "app", "apple", "apply"};
        //inserting
        for (int i=0; i<words.length; i++){
            insert(words[i]);
        }
        longestWord(root, new StringBuilder(" "));
        System.out.println(ans);
    }
}