BST_Construction_Remove_Iteration

BST_Construction_remove_iteration.py

class BST:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
    """
    the. soultion will be using a iterative approach to remove a node.
    """
    
    #first. create a parentNode that defaults to null/none because once we remove a node, 
    #we want to reassign the parentNode to the furthest right node of the BST
    def remove(self, value, parentNode=None):
    #first create the currentNode variable that stores the self for better readability
            currentNode = self
    #create a while loop that runs till the end of the tree to search the value to remove
            while currentNode is not None:
    #if the currentNode's value is greater than the value passed in, then you want to explore the left
                if value < currentNode.value:
    #if the currentNode being traversed is not the end of the BST,
    #then we want to keep traversing through the left to explore the left node further
    #set parentNode as currentNode
    #and currentNode as left node to keep traversing
                    parentNode = currentNode
                    currentNode = currentNode.left
    #if the currentNode being traversed is not the end of the BST,
    #then we want to keep traversing through the right to explore the right node further
    #set parentNode as currentNode
    #and currentNode as right node to keep traversing
                elif value > currentNode.value:
                    parentNode = currentNode
                    currentNode = currentNode.right
   #if the value that we want to remove is found, we want to create several edge cases that helps us remove the node 
                else:
   #the first case is where the node has two children nodes, 
   #if thats the case we want to find the smallest number of the right subtree and 
   #replace the node with the value we're trying to remove
                    if currentNode.left is not None and currentNode.right is not None:
   #first replace the node with the smallest value. 
   #Here, we are setting the currentNode.value as the smallest value of the right subtree
                        currentNode.value = currentNode.right.getMinValue()
   #remove the value by passing in currentNode.value(which is the value that we had just set) 
   #and the currentNode(which is the parentNode).
   #since the parentNode is default to None, we want to set the parentNode to the currentNode.value 
   #because the tree will essentially have the parentNode as None if we do not set it
                        currentNode.right.remove(currentNode.value, currentNode)
   #this case is the root node case. 
   #This is when the parent node is not present. 
   #Which means that this is the root node of the BST.
                    elif parentNode is None:
   #if the child node is the left child node,
                        if currentNode.left is not None:
   #replace the current node's value, right node and left node manually with the left node's values
                            currentNode.value = currentNode.left.value
   #we assign currentNode.right here first because we dont want to overwrite the currentNode.left early
                            currentNode.right = currentNode.left.right
                            currentNode.left = currentNode.left.left
   #if the child node is the right child node,
                        elif currentNode.right is not None:
   #replace the current node's value, right node and right node manually with the right node's values
                            currentNode.value = currentNode.right.value
   #we assing currentNode.left here first because we donmt want to overwrite the currentNode.right early\
                            currentNode.left = currentNode.right.left
                            currentNode.right = currentNode.right.right
   #if the node does not have any children node, then we will disregard it because if we delete the node, 
   #we are essentially deleting the whole BST  
                        else:
                            pass
   #if the parent node doesnt have two children nodes, and the current node is the left child node
                    elif parentNode.left == currentNode:
   #we want to reassign the parent node to the left child node if it exists, if it does not, 
   #then we want to reassign the parent node with the right child node
                        parentNode.left = currentNode.left if currentNode.left is not None else currentNode.right
   #if the parent node doesnt have two children nodes, and the current node is the right child node
                    elif parentNode.right == currentNode:
   #we want to do the same things as above and reassign either the left child node if it exists, or if it doesnt, 
   #reassign the parent node with the right child node
                        parentNode.right = currentNode.left if currentNode.left is not None else currentNode.right
                    break
            return self
        
   #create a helper function that gets the minimum value in the right subtree
        def getMinValue(self):
   #recreate a currentNode variable for better readability
            currentNode = self
   #We want to traverse through the left part of the tree all the way to the end 
   #and return the final value at the most left tree
   #if the traversal is at the end of the BST
            while currentNode.left is not None:
                currentNode = currentNode.left
   #return the left most value of the BST
            return currentNode.value