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,"");
    }
}