Binary Search Trees (BSTs) provide efficient operations for searching, inserting, and deleting elements while maintaining their sorted structure. Each of these operations leverages the BST property—where the left subtree contains values smaller than the node, and the right subtree contains values greater than the node.

In this lesson, we will cover the three primary operations on BSTs:

1. Insertion - Adding a new node while maintaining the BST structure.
2. Searching - Finding a node in the BST efficiently.
3. Deletion - Removing a node while preserving BST properties.

Each operation follows a recursive approach, breaking down the problem into smaller subproblems, making traversal more structured. Let's explore each operation in detail.

1. BST Insertion

Insertion in a Binary Search Tree (BST) requires finding the correct position while maintaining the BST property. Starting from the root, we compare the new value with the current node. If the value is smaller, we move to the left subtree; if greater, we move to the right. Once an empty spot is found, the new node is inserted.

Step-by-Step Algorithm

1. If the BST is empty, create a new node and set it as the root.
2. Start at the root and compare the new value with the current node’s value:
   • If the value is smaller, move to the left subtree.
   • If the value is greater, move to the right subtree.
3. Repeat recursively until we find an empty spot (NULL).
4. Insert the new node at the found position, maintaining the BST structure.

Time Complexity

• Best and Average Case: O(log n)
  • Each step eliminates half the remaining elements, making it logarithmic.
• Worst Case (Skewed Tree): O(n)
  • If the tree is completely unbalanced (like a linked list), insertion takes linear time.

Space Complexity

• O(h), where h is the height of the tree
• Recursive calls take stack space proportional to the tree height.

2. BST Searching

Searching in a BST efficiently finds a given value by leveraging the BST property. Like insertion, we start from the root and decide whether to move left or right based on comparisons.

Step-by-Step Algorithm

1. If the BST is empty, return "Not Found."
2. Start at the root and compare the search key with the current node’s value:
   • If the key matches, return the node.
   • If the key is smaller, move to the left subtree.
   • If the key is greater, move to the right subtree.
3. Repeat recursively until the value is found or the search ends at a NULL pointer.

Code

Time Complexity

• In a balanced BST, searching takes O(log n) because we eliminate half of the remaining elements at each step, similar to binary search.
• In the worst case (skewed tree), searching takes O(n) as we may have to traverse all nodes in a single branch.
• The best case is O(1) if the root contains the key.

Space Complexity

• Space Complexity is O(h) for recursive (O(log n) in balanced, O(n) in skewed BST).

3. BST Deletion

Deleting a node from a Binary Search Tree (BST) requires adjusting the tree structure while ensuring that the BST property remains intact. The complexity of deletion varies depending on the number of children the node has.

We need to handle three cases:

1. Leaf Node (No Children): If the node is a leaf, it is simply removed from the tree.
2. Node with One Child: If the node has only one child, we replace it with its child, bypassing the node.
3. Node with Two Children: We replace the node's value with the inorder successor (smallest value in the right subtree) and then recursively delete the successor node.

By following these steps, we ensure the BST remains valid while removing the specified node.

Step-by-Step Algorithm

1. Handle the Base Case:

   • If the tree is empty (node == null), return null as there is nothing to delete.

2. Traverse the Tree to Find the Node to Delete:

   • If the key to delete is smaller than the current node’s value (key < node.val), recursively search in the left subtree by calling delete(node.left, key).
   • If the key is greater than the current node’s value (key > node.val), recursively search in the right subtree by calling delete(node.right, key).

3. Node to be Deleted is Found:

   • If key == node.val, proceed to handle the deletion cases.

4. Case 1: Node Has No Left Child (Only Right Child or Leaf Node)

   • If node.left == null, return node.right, effectively removing the current node.

5. Case 2: Node Has No Right Child (Only Left Child)

   • If node.right == null, return node.left, effectively removing the current node.

6. Case 3: Node Has Two Children (Both Left and Right Exist)

   • Find the inorder successor, which is the smallest node in the right subtree.
   • Use the helper function minValueNode(node.right) to locate this successor.
   • Copy the inorder successor's value to the current node (node.val = successor.val).
   • Recursively delete the successor node from the right subtree using delete(node.right, successor.val).

7. Return the Updated Node:

   • After handling all cases, return the updated node to maintain the tree structure.

This algorithm ensures that the BST properties are preserved after deletion.

Code