public class PrefixProblem { static class Node { Node[] children = new Node[26]; boolean endOfWord = false; int freq; Node() { for (int i = 0; i < 26; i++) children[i] = null; freq=1; } } public static Node root = new Node(); public static void insert(String key){ Node curr=root; for(int i=0;i<key.length();i++){ int idx=key.charAt(i)-'a'; if(curr.children[idx]==null){ curr.children[idx]=new Node(); } else curr.children[idx].freq++; curr=curr.children[idx]; } curr.endOfWord=true; } public static void findPrefix(Node root, String ans){ if(root==null) return; if(root.freq == 1) { System.out.print(ans + " "); return; } for(int i=0;i<26;i++){ if(root.children[i]!=null){ findPrefix(root.children[i], ans+(char)(i+'a')); } } } public static void main(String[] args){ String[] words={"zebra","dog","duck","dove"}; for (String word : words) insert(word); root.freq=-1; findPrefix(root,""); } }