Welcome to another exciting lesson on Data Structures and Algorithms! Today, we'll learn about deleting nodes in a Binary Search Tree (BST). This concept is crucial for understanding and managing data efficiently in real-world projects. Let's dive in!
A Binary Search Tree (BST) is a binary tree data structure where each node has at most two children, the left child being less than the parent, and the right child being greater than the parent. This allows for efficient searching, insertion, and deletion of elements.
There are three cases to consider when deleting a node in a BST:
Let's explore each case with practical examples.
In a BST, a leaf node is a node without any children. To delete a leaf node, we simply remove it and adjust the pointers.
class Node:
# Node definition...
def delete_leaf(root, key):
if root is None:
return root
if root.key > key:
root.left = delete_leaf(root.left, key)
elif root.key < key:
root.right = delete_leaf(root.right, key)
else:
# If the node to be deleted is a leaf
if root.left is None and root.right is None:
return None
# If the node to be deleted has only one child
elif root.left is None:
return root.right
elif root.right is None:
return root.left
# Example usage:
root = Node(50)
root.left = Node(30)
root.right = Node(70)
root.left.left = Node(20)
root.left.right = Node(40)
root.right.left = Node(60)
root.right.right = Node(80)
delete_leaf(root, 40) # Delete the leaf node with key 40When deleting a node with one child, we replace the node with its child.
def delete_node_one_child(root, key):
if root is None:
return root
if root.key > key:
root.left = delete_node_one_child(root.left, key)
elif root.key < key:
root.right = delete_node_one_child(root.right, key)
else:
# If the node to be deleted has one child
if root.left is None:
return root.right
elif root.right is None:
return root.left
# If the node to be deleted has both children
root.key = min(root.right.keys) # Replace the key with the minimum key in the right subtree
root.right = delete_node_one_child(root.right, root.key) # Delete the found minimum node
# Example usage:
root = Node(50)
root.left = Node(30)
root.right = Node(70)
root.left.left = Node(20)
root.left.right = Node(40)
root.right.left = Node(60)
root.right.right = Node(80)
delete_node_one_child(root, 20) # Delete the node with key 20Deleting a node with two children requires a bit more effort. We find a successor (the smallest node in the right subtree) and replace the key of the node to be deleted with the successor's key. Then we delete the successor.
def find_successor(node):
current = node
while current.left is not None:
current = current.left
return current
def delete_node_two_children(root, key):
if root is None:
return root
if root.key > key:
root.left = delete_node_two_children(root.left, key)
elif root.key < key:
root.right = delete_node_two_children(root.right, key)
else:
# If the node to be deleted has two children
successor = find_successor(root.right)
root.key = successor.key
root.right = delete_node_one_child(root.right, successor.key)
# Example usage:
root = Node(50)
root.left = Node(30)
root.right = Node(70)
root.left.left = Node(20)
root.left.right = Node(40)
root.right.left = Node(60)
root.right.right = Node(80)
delete_node_two_children(root, 40) # Delete the node with key 40What is a Binary Search Tree (BST)?
What happens when we delete a leaf node in a BST?
What happens when we delete a node with one child in a BST?
What happens when we delete a node with two children in a BST?
That's it for today! We learned about deleting nodes in a Binary Search Tree (BST) with three different cases. Practice these concepts and implement the functions to reinforce your understanding. Happy coding! š