private TrieEntry<K, V> addEntry(TrieEntry<K, V> toAdd, int keyLength) {
        TrieEntry<K, V> current = root.left;
        TrieEntry<K, V> path = root;
        while(true) {
            if(current.bitIndex >= toAdd.bitIndex || current.bitIndex <= path.bitIndex) {
                toAdd.predecessor = toAdd;
                
                if (!isBitSet(toAdd.key, keyLength, toAdd.bitIndex)) {
                    toAdd.left = toAdd;
                    toAdd.right = current;
                } else {
                    toAdd.left = current;
                    toAdd.right = toAdd;
                }
               
                toAdd.parent = path;
                if (current.bitIndex >= toAdd.bitIndex) {
                    current.parent = toAdd;
                }
                
                // if we inserted an uplink, set the predecessor on it
                if(current.bitIndex <= path.bitIndex) {
                    current.predecessor = toAdd;
                }
         
                if (path == root || !isBitSet(toAdd.key, keyLength, path.bitIndex))
                    path.left = toAdd;
                else
                    path.right = toAdd;
                return toAdd;
            }
                
            path = current;
            if(!isBitSet(toAdd.key, keyLength, current.bitIndex))
                current = current.left;
            else
                current = current.right;
        }
    }