import java.util.ArrayList; //Note: All of your TrieMapInterface method implementations must function recursively //I have left the method signatures from my own solution, which may be useful hints in how to approach the problem //You are free to change/remove/etc. any of the methods, as long as your class still supports the TrieMapInterface import java.util.ArrayList; public class TrieMap implements TrieMapInterface{ TrieMapNode root; public TrieMap(){ } //Indirectly recursive method to meet definition of interface public void put(String key, String value){ } //Recursive method public void put(TrieMapNode current, String curKey, String value){ } //Indirectly recursive method to meet definition of interface public String get(String key){ return ""; } //Recursive method public String get(TrieMapNode current, String curKey){ return ""; } //Indirectly recursive method to meet definition of interface public boolean containsKey(String key){ return false; } //Recursive method public boolean containsKey(TrieMapNode current, String curKey){ return false; } //Indirectly recursive method to meet definition of interface public ArrayList getValuesForPrefix(String prefix){ return new ArrayList(); } //Recursive helper function to find node that matches a prefix public TrieMapNode findNode(TrieMapNode current, String curKey){ return null; } //Recursive helper function to get all keys in a node's subtree public ArrayList getKeys(TrieMapNode current){ return new ArrayList(); } //Indirectly recursive method to meet definition of interface public void print(){ } //Recursive method to print values in tree public void print(TrieMapNode current){ } public static void main(String[] args){ //You can add some code in here to test out your TrieMap initially //The TrieMapTester includes a more detailed test } }

import java.util.ArrayList; public interface TrieMapInterface{ //Adds the key/value pair to the TrieMap public void put(String key, String value); //Returns the object value associated with the given key //If the key is not present in the TrieMap, returns null public String get(String key); //Returns true if key is in the TrieMap, false otherwise public boolean containsKey(String key); //Returns an ArrayList of objects containing all keys that start with prefix public ArrayList getValuesForPrefix(String prefix); //Prints all values stored inside the TrieMap public void print(); }

import java.util.HashMap; public class TrieMapNode{ //Keys are characters //Values are other TrieMapNodes //This way, you can use the next character in a String to determine the next node //This allows you to progress deeper into the tree private HashMap children; private String value; public TrieMapNode(){ children = new HashMap(); value = null; } public String getValue(){ return value; } public void setValue(String newVal){ value = newVal; } public HashMap getChildren(){ return children; } }