Sorry if this is a very basic question but I don't understand why root.left or root.right is assigned to the recursive call?

I have mentioned what lines I don't understand. The full code is for reference.

Thanks for the help!

def findMin(bstNode):
    currentNode = bstNode
    while currentNode.leftChild is not None:
        currentNode = currentNode.leftChild
    return currentNode


def deleteNode(rootNode, nodeValue):
    if rootNode is None:
        return rootNode

    # these two lines (root.left/right = deleteNode)
    if nodeValue < rootNode.data:
        rootNode.leftChild = deleteNode(rootNode.leftChild, nodeValue)
    elif nodeValue > rootNode.data:
        rootNode.rightChild = deleteNode(rootNode.rightChild, nodeValue)

    else:
        if not rootNode.leftChild and not rootNode.rightChild:
            rootNode = None
    
        elif not rootNode.leftChild:
            rootNode = rootNode.rightChild
        elif not rootNode.rightChild:
            rootNode = rootNode.leftChild

        else:
            # this else statement
            temp = findMin(rootNode.rightChild)
            rootNode.data = temp.data
            rootNode.rightChild = deleteNode(rootNode.rightChild, temp.data)

    return rootNode

CodePudding user response：

The algorithm needs to traverse the tree in order to find the node you want to delete. So if we havent found the node yet, then we need to call delete node recursively on its children to keep looking for it.

CodePudding user response：

This assignment is necessary.

Take this one:

rootNode.leftChild = deleteNode(rootNode.leftChild, nodeValue)

Now imaging that rootNode.leftChild happens to be the node that needs to be deleted (because its value is nodeValue). Then rootNode.leftChild can certainly not remain unchanged, right? It needs to be assigned a new node reference. The recursive call cannot make this assignment, because it does not know what rootNode is. So the recursive call will just return the node that will take the place of the deleted node, and it is up to the caller to assign this back to where it should be stored. And that is what happens here.