Assigning local variable in recursion

Question

I have a tree and It is not a binary tree, so I want to compare all of the nodes and return the largest one, using recursion. I am having a problem of how to keep track of it, as I can't put a global variable, as it has to be local... I guess... But then if the recursion goes it resets the local variable.

def tree_max(node):
    max=1                                                                                     
    if node.left == None and node.right == None:
       if node.value>max:
          max=node.value
          return max
    elif node.left == None and node.right != None:
        return tree_max(node)
    elif node.left != None and node.right == None:
        return tree_max(node.left)
    else:
        return tree_max(node.left)

Any suggestions?

Answer 1

You don't need to keep the maximum value in a variable across all recursive calls, and by all means, not a global one. In a well-structured recursion, the result will be passed around in the return value of each recursive call. Like this:

def tree_max(node):
    maxleft  = float('-inf') if not node.left  else tree_max(node.left)
    maxright = float('-inf') if not node.right else tree_max(node.right)
    return max(node.value, maxleft, maxright)

The above assumes that node is not None, if node can be null then check for this condition before calling tree_max().

Answer 2

I'd have a generator that traverses the tree. This means you can write a min(), sum() etc without duplicating the traversal logic

def tree_traverse(node):
    if not node.left and not node.right: # if only leaf nodes have values
        yield node.value
    if node.left:
        for v in tree_traverse(node.left):
            yield v
    if node.right:
        for v in tree_traverse(node.right):
            yield v

now you can just use max(tree_traverse(node))

if all the nodes have values, you can skip the first if and dedent the yield

as @abarnert says, Python3.3 has a nice way to simplify recursive generators

def tree_traverse(node):
    if not node.left and not node.right: # if only leaf nodes have values
        yield node.value
    if node.left:
        yield from tree_traverse(node.left)
    if node.right:
        yield from tree_traverse(node.right)