TypeError: '<' is not supported between instances of 'tuple' and 'str'

Question

I have a method that creates a huffman tree that looks like this:

def buildTree(tuples) :
    while len(tuples) > 1 :
        leastTwo = tuple(tuples[0:2])                  # get the 2 to combine
        theRest  = tuples[2:]                          # all the others
        combFreq = leastTwo[0][0] + leastTwo[1][0]     #enter code here the branch points freq
        tuples   = theRest + [(combFreq,leastTwo)]     # add branch point to the end
        tuples.sort()                                  # sort it into place
    return tuples[0]            # Return the single tree inside the list

but for now I am passing a function with the following parameter:

[(1, 'b'), (1, 'd'), (1, 'g'), (2, 'c'), (2, 'f'), (3, 'a'), (5, 'e')]

I get an error like

  File "<stdin>", line 7, in buildTree
    tuples.sort()
TypeError: '<' not supported between instances of 'tuple' and 'str'

During debugging, I found that the error was in tuples.sort().

Answer 1

The error occurs because you create internal nodes in the form (priority, (node, node)). For equal priorities, Python then tries to compare the character with the leaf node (so that the second element in the tuple is (priority, symbol)node) with the tuple (node, node)from the inner node:

>>> inner = (combFreq, leastTwo)
>>> inner
(2, ((1, 'b'), (1, 'd')))
>>> theRest[1]
(2, 'c')
>>> theRest[1] < inner
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: '<' not supported between instances of 'str' and 'tuple'

huffman, , , ( ):

tuples.sort(key=lambda t: t[0])

buildTree() :

>>> buildTree([(1, 'b'), (1, 'd'), (1, 'g'), (2, 'c'), (2, 'f'), (3, 'a'), (5, 'e')])
(15, ((6, ((3, 'a'), (3, ((1, 'g'), (2, 'c'))))), (9, ((4, ((2, 'f'), (2, ((1, 'b'), (1, 'd'))))), (5, 'e')))))

, . . Python?