Write the code and explain it in as much detail as possible

A Trie or Prefix Tree is an associative array tree data structure where the keys are encoded in the structure of the tree (as opposed to being stored at a specific node) and any node can have a value which would then correspond to the key encoded in the path from that node to the root. As example consider figure 1 which encodes the following key-value-pairs: ("a", 0), ("ab", 1), ("ac", 2), ("b", 1), "ba", 0), ("bad", 1), ("baf", 3) "b" 1 Figure 1: A Trie and ("bc", 4) Your task is to implement a Trie for Strings in Java. It should support the following operations Put a key k-inserts k into the structure. If k was not associated with any value v before, associate it with 1, otherwise with v1 where v was the old value. Get a key k- return the associated value for k or 0 if no value is associated Count on a prefix k- return the sum of all associated values of the sub-tree starting at k. For example Count ("ba") on figure 1 should return 01+3-4 Distinct on a prefix k- return the number of distinct keys that have associated values on the sub-tree starting at k. For example Distinct("ba") on figure 1 should returrn 2 (for the keys "bad" and "baf"). Iterator on a prefix k-return an implementation of java.utilIterator> such that k is a prefix for all keys in the entries of the iterator and the keys are returned in ascending alphabetical order. For full points do not use an intermediate representation (e.g. a list) but have the iterator traverse the underlying tree structure directly (-5P otherwise) Note: key k in all above queries is a String such as 'a' or 'cat