Problem of The Day: Delete Node in a BST

Problem Statement

leetcode problem link

My Solution [Accepted]

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public (TreeNode?, TreeNode?) FindTarget(TreeNode node, int key, TreeNode? parent) {
        if (node == null) {
            return (null, null);
        }
        if (node.val == key) {
            return (node, parent);
        }
        var (left, leftParent) = FindTarget(node.left, key, node);
        if (left != null) {
            return (left, leftParent);
        }
        return FindTarget(node.right, key, node);
    }

    public TreeNode DeleteNode(TreeNode root, int key) {
        var (node, parent) = FindTarget(root, key, null);
        if (node == null) {
            return root;
        }
        TreeNode curr = node;
        TreeNode replaceNode = node.right;
        if (replaceNode != null) {
            while (replaceNode != null && replaceNode.left != null) {
                curr = replaceNode;
                replaceNode = replaceNode.left;
            }
        } else {
            replaceNode = node.left;
            while (replaceNode != null && replaceNode.right != null) {
                curr = replaceNode;
                replaceNode = replaceNode.right;
            }
        }

        if (curr.left == replaceNode && replaceNode != null)
            if (replaceNode.right != null)
                curr.left = replaceNode.right;
            else
                curr.left = replaceNode.left;
        if (curr.right == replaceNode && replaceNode != null)
            if (replaceNode.left != null)
                curr.right = replaceNode.left;
            else
                curr.right = replaceNode.right;

        if (replaceNode != null) {
            var leftTree = node.left;
            var rightTree = node.right;
            node.left = null;
            node.right = null;
            replaceNode.left = leftTree;
            if (replaceNode != rightTree) {
                replaceNode.right = rightTree;
            }
        }

        if (parent != null) {
            if (parent.left == node)
                parent.left = replaceNode;
            else
                parent.right = replaceNode;
        } else {
            return replaceNode;
        }
        return root;
    }
}

Editorial

Approach 1: Recursion

class Solution:
    # One step right and then always left
    def successor(self, root: TreeNode) -> int:
            root = root.right
            while root.left:
                root = root.left
            return root.val

    # One step left and then always right
    def predecessor(self, root: TreeNode) -> int:
        root = root.left
        while root.right:
            root = root.right
        return root.val

    def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
        if not root:
            return None

        # delete from the right subtree
        if key > root.val:
            root.right = self.deleteNode(root.right, key)
        # delete from the left subtree
        elif key < root.val:
            root.left = self.deleteNode(root.left, key)
        # delete the current node
        else:
            # the node is a leaf
            if not (root.left or root.right):
                root = None
            # The node is not a leaf and has a right child
            elif root.right:
                root.val = self.successor(root)
                root.right = self.deleteNode(root.right, root.val)
            # the node is not a leaf, has no right child, and has a left child
            else:
                root.val = self.predecessor(root)
                root.left = self.deleteNode(root.left, root.val)

        return root