BST Operations

Concept

To master the Binary Search Tree, you must know how to implement its three core operations: Search, Insert, and Delete.
Search and Insert are trivial. Deletion is notoriously complex and frequently asked in senior interviews.

1. Search (Lookup)

Because of the BST property, searching is identical to a Binary Search on an array. If the target is smaller, go Left. If larger, go Right.

// Time Complexity: O(log N) average, O(N) worst
function searchBST(root: TreeNode | null, val: number): TreeNode | null {
    if (root === null) return null; // Not found
    
    if (root.val === val) {
        return root; // Found it!
    } else if (val < root.val) {
        return searchBST(root.left, val);
    } else {
        return searchBST(root.right, val);
    }
}

2. Insert

Insertion always happens at the very bottom of the tree (as a new Leaf). You simply Search for the value until you hit null, and then you replace that null with the brand new node.

function insertIntoBST(root: TreeNode | null, val: number): TreeNode | null {
    // We found the empty slot where it belongs! Create and return the new node.
    if (root === null) {
        return new TreeNode(val);
    }

    if (val < root.val) {
        // The new node belongs somewhere in the left branch.
        // We set our left pointer to the result of the recursion.
        root.left = insertIntoBST(root.left, val);
    } else {
        // The new node belongs in the right branch.
        root.right = insertIntoBST(root.right, val);
    }

    // Return the unmodified current node to bubble back up the Call Stack
    return root;
}

3. Delete (The Hard One)

Deleting a node from a BST is complicated because you might be deleting a Parent node that is holding other branches. If you delete the Parent, its children are orphaned. You must rewire the tree to preserve the BST mathematical rules.

There are 3 Cases to handle when deleting a node:

1. The Node is a Leaf (No Children): Easy. Just delete it (return null to its parent).
2. The Node has 1 Child: Easy. Delete the node, and instantly connect its Parent to its single Child (bypassing the deleted node).
3. The Node has 2 Children: Hard. You cannot just pull it out, because you have two separate branches to reconnect.
   • The Trick: You find the node’s In-order Successor (the absolute smallest node in its Right branch).
   • You physically copy the Successor’s value into the node you want to delete. (This legally preserves the BST rules).
   • Then, you recursively go down the Right branch and delete the original Successor node!

function deleteNode(root: TreeNode | null, key: number): TreeNode | null {
    if (root === null) return null;

    // 1. Search for the node
    if (key < root.val) {
        root.left = deleteNode(root.left, key);
    } else if (key > root.val) {
        root.right = deleteNode(root.right, key);
    } else {
        // We found the node to delete!
        
        // Case 1 & 2: Node has 0 or 1 child
        if (root.left === null) {
            return root.right; // Bypass the node, return its right child
        } else if (root.right === null) {
            return root.left;  // Bypass the node, return its left child
        }
        
        // Case 3: Node has 2 children
        // Find the In-order Successor (The smallest value in the Right branch)
        let minNode = findMin(root.right);
        
        // Copy the successor's value into our current node
        root.val = minNode.val;
        
        // Recursively delete the original successor node from the Right branch
        root.right = deleteNode(root.right, minNode.val);
    }

    return root;
}

// Helper function to find the absolute smallest node in a branch
function findMin(node: TreeNode): TreeNode {
    while (node.left !== null) {
        node = node.left;
    }
    return node;
}

Interview Questions

Q: In the Deletion algorithm with 2 children, why do we use the “In-order Successor” (the smallest value in the Right branch)? Could we use the largest value in the Left branch instead?
A: Yes! Using the “In-order Predecessor” (the absolute largest value in the Left branch) works perfectly and is equally mathematically valid. Both choices guarantee that the new value placed in the Root will be strictly larger than everything on its left, and strictly smaller than everything on its right, preserving the global BST rule.

Q: Is there an iterative version of the Delete operation?
A: Yes, but it is notoriously lengthy and error-prone because you have to manually maintain a parent pointer as you traverse the tree so you can rewire parent.left or parent.right when you find the target node. The recursive approach is vastly preferred in interviews because setting root.left = deleteNode(...) elegantly handles the pointer rewiring implicitly through the Call Stack.