Returning the sum of all nodes in a tree through recursion

Question

I have created an algorithm for Huffman coding that creates the Huffman tree for a given set of symbols, and their pmf. My alogrithm uses my own Node class which has the instance variables string symbol, float probability, list children, string code.

I can iterate through my tree recursively as follows:

def print_codes(root):
    for child in root.children:                             # Iterate through children
        if (child.symbol):                                  # If node isn't a blank node
            print(child.symbol + " = " + child.code)        # print its original symbol and code
        if (child.children):                                # If node has children
            print_codes(child)                              # print their codes recursively

Each parent node is a blank node, and each leaf node contains one of the symbols of the albhabet I am encoding. If I wanted to find the total sum of the lengths of each node's code (only the nodes where node.symbol == True, how could I achieve this in my recursive function? Where would I return from each recursive call?

Try to apply the approach from stackoverflow.com/a/42147213/674064 . Instead of "input 1 element smaller" assume a tree one level less deep. — das-g

Eric Duminil Eric Duminil · Accepted Answer · 2017-05-03T14:21:32

It's hard to test without data, but this should bring you closer to your goal:

def recursive_len_sum(node):
    temp = 0
    if node.symbol:
        temp += len(node.code)
    for child in node.children:
        temp += recursive_len_sum(child)
    return temp

recursive_len_sum(root)

Returning the sum of all nodes in a tree through recursion

1 Answers