3

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?

Improve this question
5
  • First, fix the indentation. Commented Feb 4, 2013 at 23:22
  • 2
    Next, the whole point of a local variable is that it's local to the current function call. What exactly do you want here? If you want to pass the value down and back up, you need to max it a parameter (with a default value of 1). If you want to bind it into a closure, you need an inner function (with nonlocal, a mutable default argument, etc.). Commented Feb 4, 2013 at 23:25
  • i want a variable to keep track of my highest value, thats it Commented Feb 4, 2013 at 23:26
  • 2
    Also, don't name a variable max; that's the name of a built-in function. Commented Feb 4, 2013 at 23:31
  • 2
    Just FYI, your tree is a binary tree (since each node only has two children). It's apparently not a binary search tree (which would be sorted). Commented Feb 4, 2013 at 23:49

3 Answers 3

Reset to default
4

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().

Improve this answer
Sign up to request clarification or add additional context in comments.

11 Comments

but how it is gonna know which is the max value to return
@JackF: You pass it up the recursion chain.
@JackF yes, it's a built-in function to calculate the maximum in a series of values. I updated my answer again, now it's shorter
Doing comparisons based on None is considered bad form, since e.g. if you were doing min instead of max it'd always return None. In Python 3, this would raise a TypeError. I'd either make a list and append to it if the left/right branches exist, or maybe use float('-inf') instead of None, to be a little more explicit and portable.
@Dougal what do you suggest to use, instead of None? perhaps, float('-inf') ?
|
3

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)
Improve this answer

3 Comments

+1. Much nicer. Or, in Python 3.3, just yield from tree_traverse(node.left) instead of looping. But it may be a more radical change than the OP was looking for.
@abarnert, I wasn't going to bother since hardly anyone's using Python3.3 yet, but I'll add it to make the answer more useful in the future.
From my experience, there are more people using 3.3 than 3.0-3.2. (But still not as many as 2.7, unfortunately…)
1

This is usually done using key word arguments e.g.

def tree_max(node, max=None):
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.