Lowest Common Ancestor in a BST (LeetCode 235)

Given a BST and two nodes p and q, find their lowest common ancestor (LCA). The BST property allows an efficient traversal from root down: the LCA is the first node whose value lies between p->val and q->val (inclusive). Because the tree is ordered, moving left/right narrows down the range until we hit the node that splits the two targets.

Recursive Approach

• Function signature: TreeNode* findLCA(TreeNode* current, TreeNode* a, TreeNode* b)
• Base case: Return nullptr when current is null (though problem guarantees both nodes exist).
• Logic:
  • If current->val > a->val && current->val > b->val, the LCA lies in the leeft subtree; recurse left.
  • If current->val < a->val && current->val < b->val, recurse right.
  • Otherwise, current is the LCA – return it immediately.

class Solution {
private:
    TreeNode* lcaHelper(TreeNode* node, TreeNode* p, TreeNode* q) {
        if (!node) return nullptr;
        // Both greater: go left
        if (node->val > p->val && node->val > q->val) {
            return lcaHelper(node->left, p, q);
        }
        // Both smaller: go right
        if (node->val < p->val && node->val < q->val) {
            return lcaHelper(node->right, p, q);
        }
        // current is between p and q (or equals one of them)
        return node;
    }
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        return lcaHelper(root, p, q);
    }
};

This solution uses a single path traversal (O(h) time) without visiting the whole tree.

Insert Node into a BST (LeetCode 701)

Insert a new value into a BST while keeping the BST property. The simplest way is to traverse down the tree following the BST rule and insert at the first vacant leaf position. No tree restructuring is necessary.

Recursive Insertion with Return Value

Return the updated subtree root. When nullptr is reached, create a new node and return it; the parent call will attach it appropriately.

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        // Found the insertion point
        if (!root) {
            return new TreeNode(val);
        }
        // Decide direction based on BST order
        if (val < root->val) {
            root->left = insertIntoBST(root->left, val);
        } else { // val > root->val
            root->right = insertIntoBST(root->right, val);
        }
        return root;
    }
};

Alternative Without Return Value

If you prefer a helper that keeps track of the parent node, you can update the parent’s child pointer when a leaf is reached.

class Solution {
private:
    TreeNode* parent = nullptr;
    void insertHelper(TreeNode* cur, int val) {
        if (!cur) {
            TreeNode* newNode = new TreeNode(val);
            // parent must have been set before this call
            if (val < parent->val) parent->left = newNode;
            else                     parent->right = newNode;
            return;
        }
        parent = cur;
        if (val < cur->val) insertHelper(cur->left, val);
        else                  insertHelper(cur->right, val);
    }
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (!root) return new TreeNode(val);
        insertHelper(root, val);
        return root;
    }
};

The first method is cleaner because it avoids external state and leverages the recursive return value.

Delete Node from a BST (LeetCode 450)

Removing a node from a BST requires handling multiple cases. We find the node with value key and then deal with its children:

1. Node not found: return nullptr (or unchanged root).
2. Leaf node: delete it and return nullptr.
3. Only left child: replace node with its left child.
4. Only right child: replace node with its right child.
5. Both children present: find the inorder successor (smallest in right subtree), attach the left subtree as that successor’s left child, then replace the node by its right child.

Recursive Implementation

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (!root) return root; // Case 1
        if (root->val == key) {
            // Case 2: leaf
            if (!root->left && !root->right) {
                delete root;
                return nullptr;
            }
            // Case 3: only left
            if (!root->right) {
                TreeNode* child = root->left;
                delete root;
                return child;
            }
            // Case 4: only right
            if (!root->left) {
                TreeNode* child = root->right;
                delete root;
                return child;
            }
            // Case 5: both children
            TreeNode* successorParent = root;
            TreeNode* successor = root->right;
            while (successor->left) {
                successorParent = successor;
                successor = successor->left;
            }
            // Attach left subtree of deleted node to successor's left
            successor->left = root->left;
            // Replace root with its right child (which may be successor or its ancestor)
            TreeNode* newRoot = root->right;
            delete root;
            return newRoot;
        }
        if (key < root->val) {
            root->left = deleteNode(root->left, key);
        } else {
            root->right = deleteNode(root->right, key);
        }
        return root;
    }
};

Generic BST Deletion by Value Swap

An alternative approach ignores BST properties for deletion: swap the target node with its inorder successor (the leftmost node of the right subtree) and recurse to delete the swapped value. This requires traversing the whole tree but works for any binary tree.

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (!root) return root;
        if (root->val == key) {
            if (!root->right) {
                // No right child: replace by left child
                return root->left;
            }
            // Find inorder successor
            TreeNode* succ = root->right;
            while (succ->left) succ = succ->left;
            // Swap values and delete the successor's value recursively
            swap(root->val, succ->val);
        }
        root->left = deleteNode(root->left, key);
        root->right = deleteNode(root->right, key);
        return root;
    }
};

Both methods run in O(h) average time (h = tree height). The first is more intuitive for BSTs; the second is concise but may be harder to grasp.