How python pass by reference?

Question

I tried to implement delete a node in a BST. And here is my partial code.

def delete(node,key):
#Locate that node with value k
    cNode=node
    target=None
    while cNode:
        if cNode.value==key:
            target=cNode
            break
        elif node.value>key:
            cNode=cNode.lChild
        elif node.value<key:
            cNode=cNode.rChild
    target=None
    return node

When I tried to use the above method to delete a leaf node. I failed. when the method return, it did nothing to original BST. So what's the problem of this code? I assume it should have something about how python pass arguments by reference? But I am confused now. Many thanks in advance.

There's no code here that removes anything from your tree. You probably need to sever the link between a parent and a child — nos
– nos, Commented Jan 15, 2014 at 19:58
But I set the target node which is the leaf node to None, it should also change the original tree, right? — lexie
– lexie, Commented Jan 15, 2014 at 20:00
Python already passes values by reference; it never silently copies anything. But it doesn't pass variables by reference because that would be meaningless; Python variables aren't memory locations, they're just names in some namespace. — abarnert
– abarnert, Commented Jan 15, 2014 at 20:00
@lexie, no, target is just a local variable in your delete function, you set that to None. — nos
– nos, Commented Jan 15, 2014 at 20:00
@nos: I think the OP understands that, or he wouldn't ask the question; he just doesn't understand why it's true, or what he should do instead. — abarnert
– abarnert, Commented Jan 15, 2014 at 20:01

Martijn Pieters · Accepted Answer · 2014-01-15 20:05:09Z

target = None only rebinds the variable target to a new value, None. Whatever target was bound to before doesn't change.

You'll have to track the parent node and set it's lChild or rChild attribute to None instead.

def delete(node,key):
    cNode = node
    target = parent = None
    while cNode:
        if cNode.value == key:
            target = cNode
            break
        elif cNode.value > key:
            parent, cNode = cNode, cNode.lChild
        elif cNode.value < key:
            parent, cNode = cNode, cNode.rChild

    if target:
        if parent:
            if parent.lChild is target:
                parent.lChild = None
            else:
                parent.rChild = None
        else:
            # target is top-level node; perhaps return None in that case?
    return node

Collectives™ on Stack Overflow

How python pass by reference?

1 Answer 1

2 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Related