Finding the minimum value in a binary tree, Python

Question

I'm trying to write a function that returns the smallest value in the binary tree not a binary search tree. Here's what I've written, it's not correct.

def min(root, min_t): # min_t is the initially the value of root
    if not root:
            return min_t

    if root.key < min_t:
            min_t = root.key

    min(root.left, min_t)
    min(root.right, min_t)

    return min_t

I feel I don't understand recursion very well. I can't seem to figure out when to use the return statement with a recursive call and when to not.

Thanks for your insights!

Here's another one I've come up with, it works, but it doesn't seem most efficient:

n = []
def min_tree(root, n):
    if root:
        n += [(root.key)]
        min_tree(root.left, n)
        min_tree(root.right, n)
    return min(n)

Thoughts?

Solution 1

Michael's answer explains the way you were probably supposed to approach the problem, but he didn't explain what was wrong with your current attempt. As I understand it, your strategy was to examine each node, and keep track of the lowest value as you go, using recursion to find all the nodes. Once you've examined all the nodes, you know the result is the minimum for the entire tree. This is a perfectly valid approach, and it would have worked except that arguments don't quite work the way you seem to expect.

Python passes arguments by value, not by reference. When you assign a value to min_t using "min_t = root.key", it only takes effect inside of the function. The caller of the function does not see the new value.

You can test this with some simpler code:

def add_one_to(x):
    x = x + 1
    print "add_one_to", x

x = 2
add_one_to(x)
print x

You can see when you run the code that x was incremented inside the function but not in the top level.

This also applies when a function calls itself. Each call has its own set of local variables, and assigning to a local variable inside the function does not affect the instance that called it.

Note that some languages do allow you to pass arguments by reference. If you pass an argument by reference, then assigning that argument inside the function will also affect the caller. If Python were one of those languages, you could make min_t a reference argument, and your function would work correctly.

While Python doesn't support reference arguments directly, you can also think of a reference argument as a value that goes into the function when it is called and also is passed back to the caller when the function completes. You can do both of these things separately. To pass a value back to the caller, return that value. The caller can then assign that function to its local, and you have basically passed an argument by reference.

Here's how you could apply that to the example above:

def add_one_to(x):
    x = x + 1
    print "add_one_to", x
    return x

x = 2
x = add_one_to(x)
print x

Just add a return value and assignment, and it works as it should.

You could also apply this to your original function:

def min(root, min_t): # min_t is the initially the value of root
    if not root:
            return min_t

    if root.key < min_t:
            min_t = root.key

    min_t = min(root.left, min_t)
    min_t = min(root.right, min_t)

    return min_t

All I did was add "min_t = " before each call to min() and change your return statement to return min_t at the end. (I think you probably meant to return min_t anyway. min is the name of your function, so that wouldn't have made much sense.) I believe that version will work.

Edit: The reason your min_tree function works, in spite of all this, is that n is a list, and lists are mutable objects. When I'm was talking about "values" above, what I really meant was "object". Each variable name in python maps to a specific object. If you have code like this:

def replace_list(x):
    x = [1, 2, 3]

x = [2]
replace_list(x)
print x

The result is [2]. So, if you assign a new value to x with "x =", the caller won't see it. However, if you do this:

def replace_list(x):
    x.append(1)

x = [2]
replace_list(x)
print x

The result is [2, 1]. This is because you haven't changed the value of x; x still points to the same list. However, that list now contains an additional value. Unfortunately, the "+=" operator is confusing in this respect. You might think that "x += y" is the same as "x = x + y", but in Python that is not always the case. If "x" is a kind of object that supports "+=" specifically, then that operation will modify the object in place. Otherwise, it will be the same as "x = x + 1". Lists know what to do with "+=", so using += with a list will modify it in place, but using it with a number will not.

You can actually test this without doing any function calls:

x = [1, 2]
y = x
y += [3]
print x # [1, 2, 3]
print y # [1, 2, 3]
print x is y # True, x and y are the same object, which was modified in place

x = [1, 2]
y = x
y = y + [3]
print x # [1, 2]
print y # [1, 2, 3]
print x is y # False, y is a new object equal to x + [3]

x = 1
y = x
y += 2
print x # 1
print y # 3
print x is y # False, y is a new object equal to x + 2

Solution 2

For this particular problem, you want to traverse the entire tree and return back the smallest value seen. But in general, the basic principle of recursion is that then you call the function again, you're presented with a modified version of the same problem.

Consider your tree:

    root
   /    \
left   right

When you call the recursive function on the left sub-tree, you're once again presented with a tree. Thus, you should be able to use the same kind of logic.

The key for a recursive function is the base case and the recursive step. In your tree example, the base case is not when you've found the minimum value (how would you know?), but rather it's when you've reached the bottom of the tree (aka a leaf).

And, your recursive step is looking at each of the sub problems (bin_min(left) and bin_min(right)).

The final piece is considering the return value. The invariant is that your function has returned the minimum element it has seen. Thus, when your recursive call returns, you know it's the smallest element and then thing you need to return is the smallest element of the three possible choices (root, left_min, and right_min).

def min_bin(root):
    if not root:
        return MAX_VAL
    left_min = min_bin(root.left)
    right_min = min_bin(root.right)

    return min(left_min, right_min, root.val)

Note, this is a different solution than @Rik Poggi's. He uses tail recursion to optimize it a bit.

Solution 3

Because you'll get more out of trying to figure this out yourself than a canned solution, here are some hints. First of all, you shouldn't call it min, because of course then you can't call python's min in order to test your results. And as Michael's answer reminded me, you don't have to pass in min_t because you can test root.key instead -- but I think it's helpful to pass in min_t to understand the problem.

Besides that, your first lines are just right; well-done here. :

def tree_min(root, min_t): # min_t is the initially the value of root
    if not root:
            return min_t
    if root.key < min_t:
            min_t = root.key

Now you have to think about what to return. Basically, there are three possible minimum values. The first is min_t. The second is the minimum of the right subtree. And the third is the minimum of the left subtree. Get the latter two values (this is where the recursive call comes in), and then return the smallest value.

Comments

[isal]

Thanks for your explanation. This is exactly how I wanted to do it.