import java.util.*;

public class TrieList {
	
	static class TrieNode {
		
	    char data; 
	    LinkList<TrieNode> children = new LinkList<>();
	    boolean isEnd = false; 

	    //Constructor, Time O(1), Space O(1)
	    TrieNode(char c) { 
	        this.data = c;    
	    }  
	    
	    //find the node by char, the same functionality as children[ch] in array implementation 
	    //Time O(k), Space O(1), k is number of children of this node 
	    TrieNode getChild(char c) {
	    	if (children != null)
	    		for (TrieNode ch : children)
	    			if (ch.data == c)
	                    return ch;
	        return null;
	    }	
	}
	 
	static class Trie {
		
	    TrieNode root = new TrieNode(' '); 
	    	    	    
		//Add a word to tire, Iteration, Time O(s), Space O(s), s is word length
	    void insert(String word) {
	        if (search(word) == true) {
	            System.out.println(word + " is already in trie.");
	            return;
	        }                 
	        TrieNode node = root; 
	        for (char ch : word.toCharArray()) {	           
	            if (node.getChild(ch) == null) 
	            	node.children.add(new TrieNode(ch));
	            node = node.getChild(ch);	            		           
	        }
	        node.isEnd = true;
	    }
	    
	    //Search a word in trie, Iteration, Time O(s), Space O(1), s is word length
	    boolean search(String word) {
	        TrieNode node = root;      
	        for (char c : word.toCharArray()) {
	            if (node.getChild(c) == null)
	                return false; 
	            node = node.getChild(c);    
	        }      
	        return node.isEnd;       	         
	    }
	    	    
	    //Remove a word from trie, Iteration, Time O(s), Space O(1), s is word length
	    void delete(String word) {	 
	        if (this.search(word) == false) {
	            System.out.println(word + " does not exist in trie.");
	            return;
	        }
	        TrieNode node = root;
	        for (char ch : word.toCharArray()) {        	
	            if (node.getChild(ch) == null) 
	                return;	        
	            node = node.getChild(ch);	            
	        }
	        node.isEnd = false; 
	    }
	    
	    //Print all words in trie, call recursion function
	    //Time O(n), Space O(n), n is number of nodes in trie
	    void print() {
	    	List<String> res = new ArrayList<String>(); 
	    	helper(root, res, "" );
	    	System.out.println(res);
	    }
		
	    //recursion function, Time O(n), Space O(n), n is number of nodes in trie
	    void helper(TrieNode node, List<String> res, String prefix) {		
			if (node.isEnd)  {
				String word = prefix + node.data;
				res.add(word.substring(1)); //skip the first space from root	
			}
			for (TrieNode child : node.children) 				
				helper(child, res, prefix + node.data);						
		}		   
	}

    public static void main(String[] args) {   
    	//Build trie
        Trie trie = new Trie();
        trie.insert("ana"); 
		trie.insert("anna"); 
		trie.insert("anne");          
        trie.insert("apple");	
        trie.insert("betty");
		trie.print();	
		
		String key = "apple";
		System.out.println("Search '" + key + "': " + trie.search(key));  
			
		//Delete
		trie.delete(key);
		trie.print();	
		System.out.println("Search '" + key + "': " + trie.search(key)); 
    }
}