A Binary Search Tree (BST) is a tree data structure where each node has at most two children, referred to as the left and right child. For every node in the tree, all nodes in the left subtree are less than the node, and all nodes in the right subtree are greater. This property makes BSTs useful for efficient searching, insertion, and deletion operations.
function insert(root, value):
if root is null:
return new Node(value)
if value < root.value:
root.left = insert(root.left, value)
else:
root.right = insert(root.right, value)
return root
function search(root, value):
if root is null or root.value = value:
return root
if value < root.value:
return search(root.left, value)
return search(root.right, value)
function deleteNode(root, key):
if root is null:
return root
if key < root.value:
root.left = deleteNode(root.left, key)
elif key > root.value:
root.right = deleteNode(root.right, key)
else:
if root.left is null:
return root.right
elif root.right is null:
return root.left
minValue = findMin(root.right)
root.value = minValue
root.right = deleteNode(root.right, minValue)
return root