import java.util.*;

public class TrieMap {
	
	static class TrieNode {
		 char data;
		 HashMap<Character, TrieNode> children = new HashMap<>();     
		 boolean isEnd = false;
 		 
		//Constructor, Time O(1), Space O(1)
		 TrieNode(char c) {
			 this.data = c;
		 }
	}

	static class Trie {
		
		TrieNode root = new TrieNode(' ');
		
		//Add a word to trie, 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.children.containsKey(ch)) 
			        node.children.put(ch, new TrieNode(ch));			         			    
			    node = node.children.get(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 ch : word.toCharArray()) {
		        if (!node.children.containsKey(ch)) 
		            return false;		        
		        node = node.children.get(ch);
		    }
		    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.children.containsKey(ch)) 
	                return;	        
	            node = node.children.get(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);
	    }
		
		//recursive 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 (Character ch : node.children.keySet()) 
			     helper(node.children.get(ch), res, prefix + node.data);
		}
	}
	
	public static void main(String[] args) {       
        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)); 
	}	 
}