part 5: deletion in binary search tree

hi, this is part 5 of tree data structure, and the #day_17 of algorithms and data structure, In the last posts, we talked about the binary search tree, its advantages, disadvantages, time and space complexity of its basic operations such as searching, …

hi, this is part 5 of tree data structure, and the #day_17 of algorithms and data structure, In the last posts, we talked about the binary search tree, its advantages, disadvantages, time and space complexity of its basic operations such as searching, insertion, and also their implementation using python
In this post, we’ll discuss deletion 🙂

last posts:
+ insertion, searching in binary search tree
+ introduction to binary search tree



Deletion in the binary search tree

there are 3 cases in deletion in binary search tree (reference):

  1. if the node to be deleted is the leaf, this is the easiest case, we will only remove it without moving anything 🙂
  2. if the node to be deleted has one child, in this case, we will replace the child with the node and delete the child
  3. if the node to be deleted has two children, in this case, we need to find a successor (the min of right sub-tree) or a predecessor (the max of left sub-tree), and copy it to the node to be deleted,
    then delete the successor (or the predecessor)



Deletion implementation

before the implementation of deletion, we need to create a function that returns to us a successor.



getSuccessor function

def getSuccessor(currentNode):
    while currentNode.left:
        currentNode = currentNode.left
    return currentNode



Delete function

more details…

def delete(value: int, root):
    """
        [code is from] => https://www.geeksforgeeks.org/binary-search-tree-set-2-delete/
    """
    # if the tree is empty
    if root is None:
        return root
    # if value is smaller than the root's value
    if value < root.value:
        root.left = delete(value , root.left)
    # if value is greater than the root's value
    elif(value > root.value):
        root.right = delete(value, root.right)
    else:
        #! case1 or case2 (node has not children or has only one)
        if root.left is None:
            temp = root.right
            root = None
            return temp

        elif root.right is None:
            temp = root.left
            root = None
            return temp
        #! case: node has 2 children
        # getting  successor
        temp = getSuccessor(root.right)
        # Copy the  successor's value to the node's value
        root.value = temp.value
        # Delete the successor
        root.right = delete(temp.value, root.right)
    return root



References and useful resources

Thank you for your time!
Happy coding 🙂


Print Share Comment Cite Upload Translate
APA
Aya Bouchiha | Sciencx (2024-03-29T10:32:24+00:00) » part 5: deletion in binary search tree. Retrieved from https://www.scien.cx/2021/06/29/part-5-deletion-in-binary-search-tree/.
MLA
" » part 5: deletion in binary search tree." Aya Bouchiha | Sciencx - Tuesday June 29, 2021, https://www.scien.cx/2021/06/29/part-5-deletion-in-binary-search-tree/
HARVARD
Aya Bouchiha | Sciencx Tuesday June 29, 2021 » part 5: deletion in binary search tree., viewed 2024-03-29T10:32:24+00:00,<https://www.scien.cx/2021/06/29/part-5-deletion-in-binary-search-tree/>
VANCOUVER
Aya Bouchiha | Sciencx - » part 5: deletion in binary search tree. [Internet]. [Accessed 2024-03-29T10:32:24+00:00]. Available from: https://www.scien.cx/2021/06/29/part-5-deletion-in-binary-search-tree/
CHICAGO
" » part 5: deletion in binary search tree." Aya Bouchiha | Sciencx - Accessed 2024-03-29T10:32:24+00:00. https://www.scien.cx/2021/06/29/part-5-deletion-in-binary-search-tree/
IEEE
" » part 5: deletion in binary search tree." Aya Bouchiha | Sciencx [Online]. Available: https://www.scien.cx/2021/06/29/part-5-deletion-in-binary-search-tree/. [Accessed: 2024-03-29T10:32:24+00:00]
rf:citation
» part 5: deletion in binary search tree | Aya Bouchiha | Sciencx | https://www.scien.cx/2021/06/29/part-5-deletion-in-binary-search-tree/ | 2024-03-29T10:32:24+00:00
https://github.com/addpipe/simple-recorderjs-demo