Case $1$: Deleting a node with no children

$$ Case $2$: Deleting a node with $1$ child

$$ Case $3$: Deleting a node with $2$ children

def $\_\_$init$\_\_($self$,$ value$)$:

self.value $=$ value

self.left $=$ None

self.right $=$ None

class BST:

def $\_\_$init$\_\_($self$)$:

self.root $=$ None

def insert$($self$,$ value$)$:

if self.root is None:

self.root $=$ TreeNode$($value$)$

else:

self.$\_$insert$\_$recursively$($self$.$root, value$)$

def $\_$insert$\_$recursively$($self$,$ node, value$)$:

if value $<$ node.value:

if node.left is None:

node.left $=$ TreeNode$($value$)$

else:

self.$\_$insert$\_$recursively$($node$.$left, value$)$

elif value $>$ node.value:

if node.right is None:

node.right $=$ TreeNode$($value$)$

else:

self.$\_$insert$\_$recursively$($node$.$right, value$)$

def delete$($self$,$ value$)$:

self.root $=$ self.$\_$delete$\_$recursively$($self$.$root, value$)$

def $\_$delete$\_$recursively$($self$,$ node, value$)$:

if node is None:

return node

if value $<$ node.value:

node.left $=$ self.$\_$delete$\_$recursively$($node$.$left, value$)$

elif value $>$ node.value:

node.right $=$ self.$\_$delete$\_$recursively$($node$.$right, value$)$

else:

# Case $1$: Node with no children $($leaf node$)$

if node.left is None and node.right is None:

return None

# Case $2$: Node with one child

elif node.left is None:

return node.right

elif node.right is None:

return node.left

# Case $3$: Node with two children

else:

# Get the inorder successor $($smallest in the right subtree$)$

min$\_$larger$\_$node $=$ self.$\_$min$\_$value$\_$node$($node$.$right$)$

node.value $=$ min$\_$larger$\_$node.value

node.right $=$ self.$\_$delete$\_$recursively$($node$.$right, min$\_$larger$\_$node.value$)$

return node

def $\_$min$\_$value$\_$node$($self$,$ node$)$:

current $=$ node

while current.left is not None:

current $=$ current.left

return current

def inorder$\_$traversal$($self$,$ node$)$:

if node is not None:

self.inorder$\_$traversal$($node$.$left$)$

print$($node$.$value, end$=\text{'}\text{'})$

self.inorder$\_$traversal$($node$.$right$)$

# Example usage

bst $=$ BST$()$

bst$.$insert$(15)$

bst$.$insert$(10)$

bst$.$insert$(20)$

bst$.$insert$(8)$

bst$.$insert$(12)$

bst$.$insert$(17)$

bst$.$insert$(25)$

print$("$Inorder Traversal before deletion:"$)$

bst$.$inorder$\_$traversal$($bst$.$root$)$

print$()$

# Deleting nodes

bst$.$delete$(8)$ # Case $1$: Deleting a node with no children

bst$.$delete$(10)$ # Case $2$: Deleting a node with one child

bst$.$delete$(20)$ # Case $3$: Deleting a node with two children

print$("$Inorder Traversal after deletion:"$)$

bst$.$inorder$\_$traversal$($bst$.$root$)$

print$()$