new | Python Fiddle

def edit_distance(seq1, seq2):
    while len(seq1[0]) > 1 and len(seq2[0]) > 1:
        seq1 = seq1[0]
        seq2 = seq2[0]
    matrix = {}
    for x in range(len(seq1) + 1): 
        matrix[x, 0] = x
    for y in range(len(seq2) + 1): 
        matrix[0, y] = y
    for x in range(1, len(seq1) + 1):
        for y in range(1, len(seq2) + 1):
            if seq1[x - 1] == seq2[y - 1]:
                mismatch = 0 
            else:
                mismatch = 1
            matrix[x, y] = min(matrix[x, y - 1] + 1, matrix[x - 1, y] + 1, matrix[x - 1, y - 1] + mismatch)
    return matrix[x, y]

def joined_distance(sib1, sib2, node):
	return (edit_distance(sib1, node) + edit_distance(sib2, node) - edit_distance(sib1, sib2))/2

def edit_matrix(genes):
    distances = []
    for x in genes:
        x_dist = []
        for y in genes[:(genes.index(x))] + genes[(genes.index(y))+1:]
			x_dist += [edit_distance(x,y)]
        distances += [x_dist]
	return distances

class node:
    def __init__(self, ltree, top, rtree):
        self.top = top
        self.ltree = ltree
        self.rtree = rtree

def __repr__(self):
        return str(self.top)
    
class BT(node):
    def __init__(self, left=None, top=None, right=None):
        if top == None: # primitive
            self.rep = None
        else: # extending
            self.rep = node(left, top, right)
            
    def withEntry(self, key, value):
        return node([], [(key, value)], [])

def empty(self):
        return self.rep == None

def root(self):
        precondition(not self.empty())
        return self.rep.top

def left(self):
        precondition(not self.empty())
        return self.rep.ltree

def right(self):
        precondition(not self.empty())
        return self.rep.rtree

def size(self):
        if self.empty():
            return 0
        else:
            return self.left().size() + self.right().size() + 1

def __repr__(self): 
        #inorder traversal  
        a =[]
        if not self.empty():
            if not self.left().empty():
                a += self.left().__repr__()
            if not self.empty():
                a += [(self.root()[0][0], self.root()[0][1])]
            if not self.right().empty():
                a += self.right().__repr__()
        return a

#############
class BSTD(BT):
"""
    def rep_invariant(self):
        if self.empty():
            return True
        elif not self.left().empty():
            if self.left().root()[0][0] >= self.root()[0][0]:
                return False
        elif not self.right().empty():
            if self.right().root()[0][0] <= self.root()[0][0]:
                return False
        if self.left().rep_invariant() and self.left().rep_invariant():
            return True
	
"""
 # insert mutator without allowing duplicates
    def generate(genes):
        best = len(max(genes, key=len))
        distances = edit_matrix(genes)
        for x in distances:
            for y in x:
                if y < best:
                    best = y
            		pair = (genes[distances.index(x)], genes[x.index(y)])
					spots = (genes[distances.index(x)],genes[x.index(y)])
        distances = distances[:spots[0]] + distances[spots[0]+1:]
        distances = distances[:spots[1]] + distances[spots[1]+1:]
        while len(distances) > 0:

Python Fiddle

Python Cloud IDE