Delete Leaves With a Given Value

Given a binary tree root and an integer target, delete all the leaf nodes with value target. Note that once you delete a leaf node with value target, if its parent node becomes a leaf node and has the value target, it should also be deleted (you need to continue doing that until you cannot).

Example:

Input: root = [1,2,3,2,null,2,4], target = 2 Output: [1,null,3,null,4] Explanation: Leaf nodes with value (target = 2) are removed. After removing, new nodes become leaf nodes with value (target = 2) and are removed.

Constraints: The number of nodes in the tree is in the range [1, 3000]. 1 <= Node.val, target <= 1000

# Delete Leaves With a Given Value

This problem requires us to remove leaf nodes from a binary tree that have a specific target value. Furthermore, we need to continue this process iteratively, removing any new leaf nodes that result from the initial removal and also have the target value.

## Naive Approach

A straightforward approach would involve a recursive traversal of the binary tree. In each recursive call, we check if the current node is a leaf node and if its value matches the target. If both conditions are met, we remove the node by returning `null`. Otherwise, we recursively process the left and right subtrees.

```java
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public TreeNode removeLeafNodes(TreeNode root, int target) {
        if (root == null) return null;
        root.left = removeLeafNodes(root.left, target);
        root.right = removeLeafNodes(root.right, target);
        if (root.left == null && root.right == null && root.val == target) {
            return null;
        }
        return root;
    }
}

Optimal Approach

The naive approach is already quite efficient, as it traverses the tree only once. However, we can make it slightly more concise. The core idea remains the same: recursively traverse the tree and remove leaf nodes with the target value.

class Solution {
    public TreeNode removeLeafNodes(TreeNode root, int target) {
        if (root == null) {
            return null;
        }

        root.left = removeLeafNodes(root.left, target);
        root.right = removeLeafNodes(root.right, target);

        if (root.left == null && root.right == null && root.val == target) {
            return null;
        }

        return root;
    }
}

Big(O) Run-time Analysis

The run-time complexity is O(N), where N is the number of nodes in the binary tree. This is because we visit each node exactly once during the traversal.

Big(O) Space Usage Analysis

The space complexity is O(H), where H is the height of the binary tree. This is due to the recursive call stack. In the worst case (a skewed tree), H can be equal to N, resulting in O(N) space complexity. In the best case (a balanced tree), H is log(N), resulting in O(log(N)) space complexity.

Edge Cases

1. Empty Tree: If the input tree is empty (root == null), the function should return null.
2. Tree with a Single Node: If the tree consists of only the root node, and its value matches the target, the function should return null.
3. All Nodes with Target Value: If all nodes in the tree have the target value, the function should return null.
4. No Nodes with Target Value: If no nodes have the target value, the function should return the original tree.
5. Target Value Not an Integer: While the prompt specifies the target is an integer, handling cases of incorrect type may be applicable depending on the overall code design. Throwing an IllegalArgumentException or other runtime exception would be examples.