BST Operations: Search, Insert, Delete

What is a Binary Search Tree?

A Binary Search Tree imposes a crucial ordering property on top of the binary tree structure. This property is the key to its efficiency.

To formally define it, let's consult a clear definition.

As the article states, for any given node (let's call it root) in a BST:

1. All values in the root's left subtree must be less than root's value.
2. All values in the root's right subtree must be greater than root's value.
3. Both the left and right subtrees must themselves be binary search trees.

This recursive property ensures the entire tree is sorted, which allows us to discard half of the remaining nodes at each step of a search, much like binary search in a sorted array. This leads to an average time complexity of $O(\log n)$ for its core operations.

The TreeNode Class

Before we dive into the operations, let's define the TreeNode class we'll be using in our Python examples. This is the same structure we used for general binary trees.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

1. Search Operation

Searching for a value in a BST is a direct application of its defining properties. The algorithm is straightforward:

1. Start at the root.
2. If the tree is empty (root is None), the value is not found.
3. Compare the target value with the current node's value:
   • If they are equal, you've found the node.
   • If the target value is less than the current node's value, move to the left child.
   • If the target value is greater than the current node's value, move to the right child.
4. Repeat step 3 until the node is found or you reach a None pointer.

Here are the recursive and iterative implementations in Python.

Recursive Search

def searchBST(root: TreeNode, val: int) -> TreeNode:
    """
    Searches for a node with the given value in a BST recursively.
    Returns the node if found, otherwise None.
    """
    if not root or root.val == val:
        return root
    
    if val < root.val:
        return searchBST(root.left, val)
    else: # val > root.val
        return searchBST(root.right, val)

Iterative Search

def searchBST_iterative(root: TreeNode, val: int) -> TreeNode:
    """
    Searches for a node with the given value in a BST iteratively.
    Returns the node if found, otherwise None.
    """
    current = root
    while current:
        if val == current.val:
            return current
        elif val < current.val:
            current = current.left
        else: # val > current.val
            current = current.right
    return None

The iterative approach is often preferred in production code to avoid potential stack overflow on very deep (unbalanced) trees, and it has a slightly better space complexity profile, which we'll discuss later.

2. Insertion Operation

Inserting a new value into a BST follows a similar logic to searching. The goal is to find the correct null position where the new node can be placed without violating the BST properties.

Algorithm:

1. Search the tree for the value you want to insert.
2. The search will end at a null pointer (since the value isn't already in the tree).
3. This null position is exactly where the new node should be attached.

Let's watch a video from NeetCode, which explains this process clearly and implements it in Python.

As shown in the video, the recursive solution is particularly elegant. Here is the implementation:

def insertIntoBST(root: TreeNode, val: int) -> TreeNode:
    """
    Inserts a value into the correct position in a BST.
    Returns the root of the modified tree.
    """
    if not root:
        # Base case: found the insertion point.
        return TreeNode(val)
    
    if val < root.val:
        # Recurse down the left subtree and update the left child.
        root.left = insertIntoBST(root.left, val)
    else: # val > root.val
        # Recurse down the right subtree and update the right child.
        root.right = insertIntoBST(root.right, val)
        
    # Return the (possibly unchanged) root of the current subtree.
    return root

The key insight here is the line root.left = insertIntoBST(...). When the recursion hits the base case (if not root), it returns a new TreeNode(val), which is then assigned to the parent's left or right attribute.

      10
     /  \
    5    15
     \   /
      8 12

3. Deletion Operation

Deletion is the most complex of the three operations because you must ensure the BST properties are maintained after removing a node. There are three cases to consider.

Case 1: The node to be deleted is a leaf (no children).

This is the simplest case. You can simply remove the node by setting its parent's corresponding child pointer to null.

Case 2: The node to be deleted has one child.

This is also relatively simple. You can "promote" the child to take the place of the node being deleted by updating the parent's pointer to point to the grandchild.

Case 3: The node to be deleted has two children.

This is the most complex case. You cannot simply remove the node, as it would leave two disconnected subtrees. The strategy is:

1. Find a replacement node that can take the deleted node's place while preserving the BST order. The two standard choices are:
   • The in-order successor: the smallest node in the right subtree.
   • The in-order predecessor: the largest node in the left subtree.
2. Copy the value of the replacement node into the node you intend to delete.
3. Recursively call the delete function to remove the replacement node from its original position. Since the in-order successor (smallest in right subtree) has no left child, its deletion will fall into Case 1 or Case 2.

This multi-step process for Case 3 is a common focus in interviews. Let's watch a video that explains all three cases and implements a robust solution.

Here's a summary of the full recursive deletion logic in Python:

def deleteNode(root: TreeNode, key: int) -> TreeNode:
    """
    Deletes a node with the given key from a BST.
    Returns the root of the modified tree.
    """
    if not root:
        return None

    # 1. Find the node to delete
    if key < root.val:
        root.left = deleteNode(root.left, key)
    elif key > root.val:
        root.right = deleteNode(root.right, key)
    else: # Found the node to delete (key == root.val)
        # Case 1 & 2: Node has 0 or 1 child
        if not root.left:
            return root.right
        if not root.right:
            return root.left
        
        # Case 3: Node has two children
        # Find the in-order successor (smallest value in the right subtree)
        successor = root.right
        while successor.left:
            successor = successor.left
        
        # Replace the node's value with the successor's value
        root.val = successor.val
        
        # Recursively delete the successor from the right subtree
        root.right = deleteNode(root.right, root.val)
        
    return root

Complexity Analysis

The efficiency of BST operations depends heavily on the tree's shape.

• Worst Case: Occurs when the tree is "skewed" or "degenerate" (e.g., inserting sorted elements), effectively becoming a linked list. All operations degrade to $O(n)$.
• Space Complexity: For recursive implementations, the space complexity is $O(H)$ due to the call stack, where $H$ is the height of the tree. In the worst case, this is $O(n)$. For iterative implementations, it is $O(1)$.

Conclusion

You have now covered the three fundamental operations that define a Binary Search Tree. Understanding not just how to implement them but why they work is crucial for solving more complex tree and data-modeling problems in interviews.

Key Takeaways:

• BST Property: The left subtree is smaller, the right subtree is larger. This is the guiding principle for all operations.
• Search: A simple traversal that discards half the tree at each step, similar to binary search.
• Insertion: Search for the correct null spot and attach the new node. The recursive implementation is notably concise.
• Deletion: The most involved operation, with three distinct cases. Deleting a node with two children requires replacing it with its in-order successor (or predecessor) and then recursively deleting that successor.
• Performance: BSTs offer $O(\log n)$ average time for these operations, but this degrades to $O(n)$ if the tree becomes unbalanced.

In our next lesson, we will tackle a classic interview question that builds directly on what you've learned today: validating if a given binary tree is a valid BST. This will test your understanding of the BST properties in a subtle and interesting way.