import java.util.*;

public class TrieArray {
	//don't use 26 if there is space or any other special characters
	static final int NUM_OF_CHARS = 128 ;
	
	static class TrieNode {
		char data; 
	    TrieNode[] children = new TrieNode[NUM_OF_CHARS]; 	    
	    boolean isEnd;	
	    
		//Constructor, Time O(1), Space O(1)
		TrieNode(char c) {
			data = c;
		}	    	    
	}
 
	static class Trie {
		
		TrieNode root = new TrieNode(' ');
	
		//Inserts a word into the 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[ch] == null) 
		    		node.children[ch] = new TrieNode(ch);
		        node = node.children[ch];       
		    }
		    node.isEnd = true;
	    }
	    
	    //Find 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[ch] == null)  
	            	return false;
	            node = node.children[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[ch] == null) 
	                return;	        
	            node = node.children[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 == null ) //base condition			
				return;		
			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[]) { 
		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("find " + key + ": " + trie.search(key));
        
        trie.delete(key);
        trie.print();
        System.out.println("find " + key + ": " + trie.search(key));
	}
}