# Delete Leaves With a Given Value
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/delete-leaves-with-a-given-value)
Canonical: https://scaleengineer.com/dsa/problems/delete-leaves-with-a-given-value
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Tree, Binary Tree
---
## Problem
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 1:**

**![](https://assets.glich.co/dsa/delete-leaves-with-a-given-value/image0.png)**

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

**Example 2:**

**![](https://assets.glich.co/dsa/delete-leaves-with-a-given-value/image1.png)**

**Input:** root = [1,3,3,3,2], target = 3
**Output:** [1,3,null,null,2]

**Example 3:**

**![](https://assets.glich.co/dsa/delete-leaves-with-a-given-value/image2.png)**

**Input:** root = [1,2,null,2,null,2], target = 2
**Output:** [1]
**Explanation:** Leaf nodes in green with value (target = 2) are removed at each step.

**Constraints:**

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

# Approaches
## Iterative Deletion in Passes
This approach involves repeatedly scanning the entire tree to find and remove leaf nodes that match the `target` value. This process is looped until a full scan of the tree results in no deletions. This ensures that any parent node that becomes a leaf after its children are removed is also considered for deletion in a subsequent pass.
**Time:** O(N * H), where N is the number of nodes and H is the height of the tree. Each pass requires a full tree traversal (O(N)). In the worst-case scenario of a skewed tree, we might only remove one leaf per pass, requiring H passes. This leads to a total time complexity of O(N^2). · **Space:** O(H) for the recursion stack used by the traversal function in each pass. For a skewed tree, this can be O(N).
**Pros:** The logic is straightforward: keep cleaning the tree until it's stable.
**Cons:** Very inefficient due to the need for multiple full traversals of the tree.; The implementation can be complex, especially handling parent pointers and the root node correctly.
### Explanation
The core idea is to simulate the cascading deletion by iterating. In each pass, we traverse the tree and remove all nodes that are *currently* leaves and have the value `target`. Since removing a leaf might cause its parent to become a new leaf with the `target` value, we must repeat the entire process. The loop terminates when a full traversal is completed without any nodes being removed.

This requires a traversal function that can modify the tree structure, which means it needs a reference to the parent of the node being considered for deletion.

```java
/**
 * Definition for a binary tree node.
 * public 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) {
        // A dummy root helps simplify parent tracking for the actual root.
        TreeNode dummy = new TreeNode(0);
        dummy.left = root;

        boolean changed = true;
        while (changed) {
            // We assume no changes will be made in this pass initially.
            changed = false;
            if (scanAndRemove(dummy, target)) {
                changed = true;
            }
        }
        return dummy.left;
    }

    // Scans the tree once and removes current leaves with the target value.
    // Returns true if at least one node was removed.
    private boolean scanAndRemove(TreeNode node, int target) {
        if (node == null) {
            return false;
        }

        boolean deleted = false;
        // Check left child
        if (node.left != null && node.left.left == null && node.left.right == null && node.left.val == target) {
            node.left = null;
            deleted = true;
        }
        // Check right child
        if (node.right != null && node.right.left == null && node.right.right == null && node.right.val == target) {
            node.right = null;
            deleted = true;
        }

        // Recurse and combine results
        boolean leftChanged = scanAndRemove(node.left, target);
        boolean rightChanged = scanAndRemove(node.right, target);

        return deleted || leftChanged || rightChanged;
    }
}
```
*Note: The provided code is a conceptual illustration of an iterative pass-based approach. The logic is slightly simplified for clarity.*
### Algorithm
- Create a loop that continues as long as changes are made to the tree in a pass.
- In each pass, traverse the tree from the root.
- For each node, check if its children are leaf nodes with the `target` value.
- If a child is a leaf to be deleted, set the corresponding child pointer (`left` or `right`) to `null`.
- Keep a flag to track if any node was deleted in the current pass.
- If the flag is `false` after a full pass, no more deletions are possible, so exit the loop.
- Handle the edge case where the root itself becomes a leaf and needs to be deleted.

## Single-Pass Recursive Post-Order Traversal
This optimal solution leverages a single post-order traversal. A post-order traversal (Left-Right-Node) ensures that when we visit a node, its left and right subtrees have already been processed and pruned. This allows us to check if the current node has become a leaf with the target value and decide whether to delete it, all within one pass.
**Time:** O(N), where N is the total number of nodes in the tree. Each node is visited and processed exactly once. · **Space:** O(H), where H is the height of the tree. This space is used by the recursion stack. In the worst case of a completely unbalanced (skewed) tree, H can be equal to N, making the space complexity O(N). For a balanced tree, it would be O(log N).
**Pros:** Optimal time complexity of O(N).; Elegant, concise, and easy-to-read recursive solution.; Correctly handles the cascading deletion effect in a single pass.
**Cons:** For extremely deep trees, a recursive solution could potentially lead to a `StackOverflowError`. However, given the problem constraints (up to 3000 nodes), this is not a practical concern.
### Explanation
The function recursively calls itself on its children first. The return value of the recursive call is the new root of the processed subtree, which could be `null` if the entire subtree was deleted. The parent node then updates its child pointers with these return values.

After the recursive calls for the left and right children return, we examine the current node. Because its children may have been removed, the current node might now be a leaf. If it is a leaf and its value matches the `target`, the function returns `null`, effectively signaling its parent to delete it. Otherwise, it returns the node itself.

```java
/**
 * Definition for a binary tree node.
 * public 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) {
        // Base case: if the node is null, there's nothing to do.
        if (root == null) {
            return null;
        }

        // 1. Recurse on the left and right children first (Post-order).
        // Update the children with the result of the recursive call.
        root.left = removeLeafNodes(root.left, target);
        root.right = removeLeafNodes(root.right, target);

        // 2. Process the current node.
        // Check if it has become a leaf node with the target value.
        if (root.left == null && root.right == null && root.val == target) {
            // This node needs to be deleted. Return null to its parent.
            return null;
        }

        // If the node is not a leaf to be deleted, return it.
        return root;
    }
}
```
### Algorithm
- Define a recursive function `removeLeafNodes(node, target)` that returns a `TreeNode`.
- **Base Case:** If `node` is `null`, return `null`.
- **Recursive Step (Post-order):**
  - Call `removeLeafNodes` on the left child: `node.left = removeLeafNodes(node.left, target)`.
  - Call `removeLeafNodes` on the right child: `node.right = removeLeafNodes(node.right, target)`.
- **Process Node:**
  - After the children have been processed, check if the current `node` is a leaf (`node.left == null && node.right == null`) and if `node.val == target`.
  - If both conditions are true, return `null` to remove the node.
  - Otherwise, return the `node` itself.
- The initial call is `removeLeafNodes(root, target)`, and its result is the new root of the final tree.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public 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 ; } }
```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode * removeLeafNodes ( TreeNode * root , int target ) { if ( ! root ) { return nullptr ; } root -> left = removeLeafNodes ( root -> left , target ); root -> right = removeLeafNodes ( root -> right , target ); if ( ! root -> left && ! root -> right && root -> val == target ) { return nullptr ; } return root ; } };
```

### Python

```python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def removeLeafNodes ( self , root : Optional [ TreeNode ], target : int ) -> Optional [ TreeNode ]: if root is None : return None root . left = self . removeLeafNodes ( root . left , target ) root . right = self . removeLeafNodes ( root . right , target ) if root . left is None and root . right is None and root . val == target : return None return root
```