Python classes -- mutability

Question

Im having a problem with python.. I have a binary tree node type:

class NODE:
        element = 0
        leftchild = None
        rightchild = None

And I had to implement a function deletemin:

def DELETEMIN( A ):
        if A.leftchild == None:
                retval = A.element
                A = A.rightchild
                return retval
        else:
                return DELETEMIN( A.leftchild )

Yet, when I try to test this on the binary tree:

  1
 / \
0   2

It should delete 0, by just setting it to null but instead, i get this:

  0
 / \
0   2

Why can I not nullify a node within a function in python? Is their a way to do this?

Answer 1

Python passes arguments by object-reference, just like java, not by variable-reference. When you assign to a local variable (including an argument) to a new value, you're changing only the local variable, nothing else (don't confuse that with calling mutators or assigning to ATTRIBUTES of objects: we're talking about assignments to barenames).

The preferred solution in Python is generally to return multiple values, as many as you need, and assign them appropriately in the caller. So deletemin would return two values, the current returnval and the modified node, and the caller would assign the latter as needed. I.e.:

def DELETEMIN( A ):
        if A.leftchild is None:
                return A.element, A.rightchild
        else:
                return DELETEMIN( A.leftchild )

and in the caller, where you previously had foo = DELETEMIN( bar ), you'd use instead

foo, bar = DELETEMIN( bar )

Peculiar capitalization and spacing within parentheses, BTW, but that's another issue;-).

There is no way to get "a pointer or reference to a caller's barename" (in either Python or Java) in the way you could, e.g., in C or C++. There are other alternative approaches, but they require different arrangements than you appear to prefer, so I recommend the multiple return values approach as here indicated.

Answer 2

class Node:
    element = 0;
    left_child = None
    right_child = None

def delete_min( A ):
    if A.left_child is None:
        return A.right_child
    else:
        A.left_child = delete_min(A.left_child)
        return A

tree = delete_min(tree)