Untitled

 public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return null; // Key not found
        }

        // Step 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 {
            // Step 2: Node to be deleted found
            // Case 1: Node has no children or one child
            if (root.left == null) {
                return root.right; // Replace node with right child
            } else if (root.right == null) {
                return root.left; // Replace node with left child
            }

            // Case 2: Node has two children
            // Find the in-order successor (smallest value in the right subtree)
            TreeNode successor = findMin(root.right);
            root.val = successor.val; // Replace root's value with successor's value
            // Delete the in-order successor
            root.right = deleteNode(root.right, successor.val);
        }
        return root;
    }

    private TreeNode findMin(TreeNode node) {
        while (node.left != null) {
            node = node.left;
        }
        return node; // Smallest value
    }


    // Iterative
        public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return null; // Tree is empty
        
        TreeNode parent = null; // To track the parent of the node to delete
        TreeNode current = root;

        // Step 1: Search for the node to delete
        while (current != null && current.val != key) {
            parent = current;
            if (key < current.val) {
                current = current.left;
            } else {
                current = current.right;
            }
        }

        if (current == null) return root; // Key not found in the tree

        // Step 2: Delete the node
        // Case 1: Node to delete has no children (leaf node)
        if (current.left == null && current.right == null) {
            if (current == root) {
                return null; // If the root itself is the node to delete
            }
            if (parent.left == current) {
                parent.left = null;
            } else {
                parent.right = null;
            }
        }
        // Case 2: Node to delete has one child
        else if (current.left == null || current.right == null) {
            TreeNode child = (current.left != null) ? current.left : current.right;
            if (current == root) {
                return child; // Replace root with its child
            }
            if (parent.left == current) {
                parent.left = child;
            } else {
                parent.right = child;
            }
        }
        // Case 3: Node to delete has two children
        else {
            // Find the in-order successor (smallest in right subtree)
            TreeNode successor = current.right;
            TreeNode successorParent = current;
            while (successor.left != null) {
                successorParent = successor;
                successor = successor.left;
            }

            // Replace the current node's value with successor's value
            current.val = successor.val;

            // Delete the in-order successor
            if (successorParent.left == successor) {
                successorParent.left = successor.right;
            } else {
                successorParent.right = successor.right;
            }
        }

        return root;
    }