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.

Answer 1

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