Select Page

Binary Search Tree (BST) is a type of binary tree in which the value of each node in the left subtree is less than or equal to the value of the root node, and the value of each node in the right subtree is greater than the value of the root node. This property allows for efficient searching, insertion, and deletion operations.

Insertion in BST:

To insert a new node into a BST, you start at the root and compare the value of the new node with the value of the current node:

  1. If the new node’s value is less than the current node’s value, you move to the left subtree.
  2. If the new node’s value is greater than the current node’s value, you move to the right subtree.
  3. Repeat steps 1 and 2 until you reach a null child pointer, indicating the appropriate position for insertion.

Once you find the correct position, insert the new node as a leaf node at that position.

Here’s a Python implementation for insertion in a BST:

python
class TreeNode:

def __init__(self, value):

self.value = value

self.left = None

self.right = None

def insert(root, value):
if root is None:
return TreeNode(value)

if value < root.value:
root.left = insert(root.left, value)
elif value > root.value:
root.right = insert(root.right, value)

return root

Deletion in BST:

Deleting a node from a BST involves three cases:

  1. Deleting a Leaf Node: If the node to be deleted has no children, simply remove it from the tree.
  2. Deleting a Node with One Child: If the node to be deleted has only one child, replace the node with its child.
  3. Deleting a Node with Two Children: If the node to be deleted has two children, replace it with the minimum node from its right subtree (or maximum node from its left subtree). Then, recursively delete the minimum node from the right subtree (or maximum node from the left subtree).

Here’s a Python implementation for deletion in a BST:

python
def delete(root, value):

if root is None:

return root

if value < root.value:
root.left = delete(root.left, value)
elif value > root.value:
root.right = delete(root.right, value)
else:
if root.left is None:
return root.right
elif root.right is None:
return root.left

min_right_subtree = find_min(root.right)
root.value = min_right_subtree.value
root.right = delete(root.right, min_right_subtree.value)

return root

def find_min(node):
while node.left is not None:
node = node.left
return node

Both insertion and deletion operations in a BST maintain the binary search tree property after completion