BST Operations (Insert, Delete, Search)

Binary Search Trees (BSTs): Core Operations

The true power of Binary Search Trees lies in their efficient operations for managing ordered data. The primary operations are searching for an element, inserting a new element, and deleting an existing element. Each of these operations leverages the BST property to achieve logarithmic time complexity in the average case.

---

1. The BST Node Structure

Before diving into operations, let's define a typical node structure for a BST. Each node will hold a key (the value being stored) and references to its left and right children.

class Node {
  constructor(key) {
    this.key = key;
    this.left = null;  // Reference to the left child node
    this.right = null; // Reference to the right child node
  }
}

---

2. Search Operation

Searching for a specific key in a BST is similar to binary search. We start at the root and compare the target key with the current node's key.

• Algorithm:

  1. Start at the root.
  2. If the target key matches the current node's key, the node is found.
  3. If the target key is less than the current node's key, move to the left child.
  4. If the target key is greater than the current node's key, move to the right child.
  5. Repeat until the node is found or a null reference is encountered (meaning the key is not in the tree).

• Pseudocode (Iterative):

  function search(root, target) {
    let currentNode = root;
    while (currentNode !== null) {
      if (target === currentNode.key) {
        return currentNode; // Found the node
      } else if (target < currentNode.key) {
        currentNode = currentNode.left; // Go left
      } else {
        currentNode = currentNode.right; // Go right
      }
    }
    return null; // Key not found
  }
  

• Time Complexity: O(H), where H is the height of the tree. In a balanced BST, this is O(log N). In the worst case (skewed tree), it's O(N).

---

3. Insert Operation

Inserting a new key into a BST involves finding the correct position where the BST property will be maintained.

• Algorithm:

  1. Start at the root.
  2. If the tree is empty, the new key becomes the root.
  3. Compare the new key with the current node's key.
  4. If the new key is less than the current node's key, go to the left child. If the left child is null, insert the new node there.
  5. If the new key is greater than the current node's key, go to the right child. If the right child is null, insert the new node there.
  6. Handle duplicates according to your chosen policy (e.g., ignore, store count, or place on one side).

• Pseudocode (Iterative):

  function insert(root, key) {
    const newNode = new Node(key);
    if (root === null) {
      return newNode; // New node becomes the root
    }
  
    let currentNode = root;
    while (true) {
      if (key === currentNode.key) {
        // Handle duplicates: here, we'll just return the existing root
        // Other policies: store count, or insert to left/right based on rule
        return root;
      } else if (key < currentNode.key) {
        if (currentNode.left === null) {
          currentNode.left = newNode;
          break;
        }
        currentNode = currentNode.left;
      } else { // key > currentNode.key
        if (currentNode.right === null) {
          currentNode.right = newNode;
          break;
        }
        currentNode = currentNode.right;
      }
    }
    return root;
  }
  

• Time Complexity: O(H), where H is the height of the tree. O(log N) average, O(N) worst case.

---

4. Delete Operation

Deleting a node from a BST is the most complex operation because it needs to maintain the BST property after removal. There are three main cases:

• Case 1: Node is a Leaf Node (no children):

  • Simply remove the node.

• Case 2: Node has One Child:

  • Replace the node with its single child.

• Case 3: Node has Two Children:

  • This is the trickiest case. We need to find a replacement node that will maintain the BST property. The common strategy is to find the node's inorder successor (the smallest node in its right subtree) or inorder predecessor (the largest node in its left subtree).
  • Replace the deleted node's key with the successor's key.
  • Then, delete the inorder successor node (which will fall into Case 1 or Case 2).

• Pseudocode (Recursive for simplicity, iterative is also possible):

  function deleteNode(root, key) {
    if (root === null) {
      return null; // Base case: empty tree or key not found
    }
  
    // Traverse to find the node to delete
    if (key < root.key) {
      root.left = deleteNode(root.left, key);
    } else if (key > root.key) {
      root.right = deleteNode(root.right, key);
    } else {
      // Node with only one child or no child
      if (root.left === null) {
        return root.right;
      } else if (root.right === null) {
        return root.left;
      }
  
      // Node with two children: Get the inorder successor (smallest in the right subtree)
      let tempNode = root.right;
      while (tempNode.left !== null) {
        tempNode = tempNode.left;
      }
      root.key = tempNode.key; // Copy the inorder successor's content to this node
  
      // Delete the inorder successor
      root.right = deleteNode(root.right, tempNode.key);
    }
    return root;
  }
  

• Time Complexity: O(H), where H is the height of the tree. O(log N) average, O(N) worst case.

---

Key Takeaway: Search, insert, and delete operations in a BST are fundamental. While search and insert are relatively straightforward, deletion requires careful handling of three distinct cases to preserve the tree's integrity. The efficiency of all these operations is heavily dependent on the tree's balance, highlighting the importance of balanced BST variants for consistent performance.