Binary Search Tree (BST) Operations: Insert, Delete, Search

A Binary Search Tree (BST) is a binary tree data structure with the following properties:

  • The left subtree of a node contains only nodes with keys less than the node's key.
  • The right subtree of a node contains only nodes with keys greater than the node's key.
  • Both the left and right subtrees must also be binary search trees.

1. Insert Operation

The insert operation adds a new node with a given key to the BST while maintaining its properties.

Algorithm:

  1. If the tree is empty, create a new node and set it as the root.
  2. If the tree is not empty, compare the key to be inserted with the root's key:
    • If the key is less than the root's key, recursively insert into the left subtree.
    • If the key is greater than the root's key, recursively insert into the right subtree.
  3. If the key already exists, typically no action is taken (assuming duplicate keys are not allowed).

Time Complexity: O(h), where h is the height of the tree.

2. Delete Operation

The delete operation removes a node with a given key from the BST while maintaining its properties.

Algorithm:

  1. Search for the node to be deleted.
  2. If the node is found, there are three cases: a. Node has no children (leaf node):
    • Simply remove the node. b. Node has one child:
    • Replace the node with its child. c. Node has two children:
    • Find the inorder successor (smallest node in the right subtree).
    • Replace the node's key with the inorder successor's key.
    • Delete the inorder successor.

Time Complexity: O(h), where h is the height of the tree.

3. Search Operation

The search operation finds a node with a given key in the BST.

Algorithm:

  1. Start at the root.
  2. Compare the search key with the current node's key:
    • If they match, return the current node.
    • If the search key is less than the current node's key, recursively search the left subtree.
    • If the search key is greater than the current node's key, recursively search the right subtree.
  3. If the end of the tree is reached without finding the key, return null or indicate that the key was not found.

Time Complexity: O(h), where h is the height of the tree.

Note: In a balanced BST, the height h is approximately log(n), where n is the number of nodes. However, in the worst case (a skewed tree), h can be n, leading to O(n) time complexity for all operations.