Return dictionary from recursive function

Question

I have a binary search tree where each node represents a game length. I have to return a dictionary where the key is the length of the game and the value is the number of games that are of that length. The recursion call goes through every node in the tree but it returns an incorrect dictionary. I'm positive that the problem is how I'm returning the dictionary. Any help will be appreciated

game_len = {}
if not node.children:
 key = len(node.possible_next_moves())
 if key not in game_len:
 game_len[key] = 1
 else:
 game_len[key] += 1
else:
 key = len(node.possible_next_moves())
 if key not in game_len:
 game_len[key] = 1
 else:
 game_len[key] += 1
 [game_lengths(child) for child in node.children] 
return game_len

• matsjoyce: Could you add to the question how your code does not work?

Answer 1

In general, there are two ways to handle the return values from a recursive algorithm. Either you can collect the return values from your recursive calls and combine them, or you can pass in an extra mutable argument which the recursive calls can modify. I think the latter is likely to be best in this situation, since dictionaries are easy to mutate in place but not especially easy to merge together:

def game_lengths(node, result=None):
 if result is None:
 result = {}
 #... add a value to the result dict, handle base cases, etc.
 for child in node.children:
 game_lengths(child, result)
 return result