### Question:
BinaryTrie implements Serializable { public Match longestPrefixMatch(BitSequence querySequence) { Node curr = bt; for (int i = 0; i < querySequence.length(); i += 1) { if (curr.isLeaf()) { return new Match(querySequence.firstNBits(i), curr.ch); } else { int bit = querySequence.bitAt(i); if (bit == 0) { curr = curr.left; } else { curr = curr.right; } } } return new Match(querySequence, curr.ch); } BinaryTrie(Map<Character, Integer> frequencyTable); Match longestPrefixMatch(BitSequence querySequence); Map<Character, BitSequence> buildLookupTable();  }### Answer:
@Test public void bestPrefixMatchWithExactMatches() { System.out.println("Testing that bestPrefixMatch works with exact matches."); Map<Character, Integer> frequencyTable = new HashMap<Character, Integer>(); frequencyTable.put('a', 1); frequencyTable.put('b', 2); frequencyTable.put('c', 4); frequencyTable.put('d', 5); frequencyTable.put('e', 6); BinaryTrie trie = new BinaryTrie(frequencyTable); BitSequence shouldBeA = new BitSequence("000"); Match m = trie.longestPrefixMatch(shouldBeA); assertEquals((char) 'a', (char) m.getSymbol()); assertEquals(shouldBeA, m.getSequence()); BitSequence shouldBeE = new BitSequence("11"); m = trie.longestPrefixMatch(shouldBeE); assertEquals((char) 'e', (char) m.getSymbol()); assertEquals(shouldBeE, m.getSequence()); }
@Test public void bestPrefixMatchWithLongerBitSequences() { System.out.println("Testing that bestPrefixMatch works with long string matches."); Map<Character, Integer> frequencyTable = new HashMap<Character, Integer>(); frequencyTable.put('a', 1); frequencyTable.put('b', 2); frequencyTable.put('c', 4); frequencyTable.put('d', 5); frequencyTable.put('e', 6); BinaryTrie trie = new BinaryTrie(frequencyTable); BitSequence shouldBeA = new BitSequence("0001010001"); Match m = trie.longestPrefixMatch(shouldBeA); assertEquals((char) 'a', (char) m.getSymbol()); BitSequence justA = new BitSequence("000"); assertEquals(justA, m.getSequence()); BitSequence shouldBeE = new BitSequence("11000110001"); m = trie.longestPrefixMatch(shouldBeE); assertEquals((char) 'e', (char) m.getSymbol()); BitSequence justE = new BitSequence("11"); assertEquals(justE, m.getSequence()); BitSequence shouldBeAE = new BitSequence("00011"); m = trie.longestPrefixMatch(shouldBeA); assertEquals((char) 'a', (char) m.getSymbol()); assertEquals(justA, m.getSequence()); BitSequence remainingBits = shouldBeAE.allButFirstNBits(m.getSequence().length()); m = trie.longestPrefixMatch(remainingBits); assertEquals((char) 'e', (char) m.getSymbol()); assertEquals(justE, m.getSequence()); }