Huffman coding error

Question

I am trying to implement the Huffman coding algorithm.

I have written the following code

def make_leaf(symbol,weight):
    return (symbol,weight)

def is_leaf(x):
    return isinstance(x,tuple) and \
           len(x)==2 and \
           isinstance(x[0],str) and \
           isinstance(x[1],int)

def get_leaf_symbol(leaf):
    return leaf[0]

def get_leaf_freq(leaf):
    return leaf[1]

def get_left_branch(huff_tree):
    return huff_tree[0]

def get_right_branch(huff_tree):
    return huff_tree[1]


def get_symbols(huff_tree):
    if is_leaf(huff_tree):
        return [get_leaf_symbol(huff_tree)]
    else:
        return huff_tree[2]

def get_freq(huff_tree):
    if is_leaf(huff_tree):
        return get_leaf_freq(huff_tree)
    else:
        huff_tree[3]


def make_huffman_tree(left_branch,right_branch):
    return [left_branch,
            right_branch,
            get_symbols(left_branch) + get_symbols(right_branch),
            get_freq(left_branch) + get_freq(right_branch)]

However when I try to build a binary tree by writing the following code

ht01 = make_huffman_tree(make_leaf('A', 4),
                        make_huffman_tree(make_leaf('B',2),
                                          make_huffman_tree(make_leaf('D', 1),
                                                         make_leaf('C', 1))))

I get an error like this:

Traceback (most recent call last):
  File "C:\Users\Swadesh\Documents\Anmol\Python\huffman trial.py", line 47, in <module>
    make_leaf('C', 1))))
  File "C:\Users\Swadesh\Documents\Anmol\Python\huffman trial.py", line 41, in make_huffman_tree
    get_freq(left_branch) + get_freq(right_branch)]
TypeError: unsupported operand type(s) for +: 'int' and 'NoneType'

I don't know how to resolve this error. Can someone help me out ?

Thanks

svk svk · Accepted Answer · 2013-04-25T07:20:33

You're missing a 'return' on the last line of your get_freq() function.

If you don't return anything from a function, Python will use None as the return value.

When you then try to use this return value in an addition, you get the error you posted (you can't add None to an integer).

Huffman coding error

1 Answers