protected TrieEntry<K,V> lowerEntry(K key) {
        // Basically:
        // Follow the steps of adding an entry, but instead...
        //
        // - If we ever encounter a situation where we found an equal
        //   key, we return it's previousEntry immediately.
        //
        // - If we hit root (empty or not), return null.
        //
        // - If we have to add a new item, we temporarily add it,
        //   find the previousEntry to it, then remove the added item.
        //
        // These steps ensure that the returned value is always just before
        // the key or null (if there was nothing before it).
        
        // TODO: Cleanup so that we don't actually have to add/remove from the
        //       tree.  (We do it here because there are other well-defined 
        //       functions to perform the search.)
        int keyLength = length(key);
        
        if (keyLength == 0) {
            return null; // there can never be anything before root.
        }
        
        TrieEntry<K, V> found = getNearestEntryForKey(key, keyLength);
        if (key.equals(found.key))
            return previousEntry(found);
        
        int bitIndex = bitIndex(key, found.key);
        if (isValidBitIndex(bitIndex)) {
            TrieEntry<K, V> added = new TrieEntry<K, V>(key, null, bitIndex);
            addEntry(added, keyLength);
            incrementSize(); // must increment because remove will decrement
            TrieEntry<K, V> prior = previousEntry(added);
            removeEntry(added);
            modCount -= 2; // we didn't really modify it.
            return prior;
        } else if (isNullBitKey(bitIndex)) {
            return null;
        } else if (isEqualBitKey(bitIndex)) {
            return previousEntry(found);
        }

        // we should have exited above.
        throw new IllegalStateException("invalid lookup: " + key);
    }