Code Implementation

# 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: TreeNode, target: int) -> TreeNode:
        if not root:
            return None
        root.left = self.removeLeafNodes(root.left, target)
        root.right = self.removeLeafNodes(root.right, target)
        if not root.left and not root.right and root.val == target:
            return None
        return root
      

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

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) {
            delete root;
            return nullptr;
        }
        return root;
    }
};
      

// 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;
    }
}
      

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} target
 * @return {TreeNode}
 */
var removeLeafNodes = function(root, target) {
    if (!root) return null;
    root.left = removeLeafNodes(root.left, target);
    root.right = removeLeafNodes(root.right, target);
    if (!root.left && !root.right && root.val === target) {
        return null;
    }
    return root;
};
      

Problem Description

Given the root of a binary tree and an integer target, remove all leaf nodes from the tree that have the value target. If, after removing such leaves, new leaves are formed with the value target, remove those as well. Repeat this process until no more leaves with value target exist.

You must return the root of the modified tree. If the entire tree is deleted, return null.

• There is only one valid way to remove the leaves in the described fashion.
• Do not reuse or reconstruct nodes unnecessarily.
• All node values and target are integers.

Thought Process

At first glance, this problem seems similar to simply removing leaves with a certain value. However, the twist is that removing leaves may create new leaves that also need to be checked and possibly removed. This recursive aspect means we must process the tree in a way that checks all possible leaves, even those that become leaves only after earlier deletions.

A brute-force approach might involve repeatedly traversing the tree and removing target-valued leaves until none remain, but this would be inefficient. Instead, we can use recursion to process the tree from the bottom up, always ensuring that by the time we consider a node, its children have already been processed.

This leads to the realization that a post-order traversal is ideal: we visit the left and right children before deciding whether to remove the current node.

Solution Approach

We solve this problem using recursion and post-order traversal. Here's the step-by-step process:

1. Base Case: If the current node is null, return null. This handles empty subtrees.
2. Recursive Step: Recursively process the left and right children by calling the function on root.left and root.right. Update the current node's left and right pointers with the results.
3. Leaf Check: After processing children, check if the current node is now a leaf (both left and right are null) and its value is equal to target.
4. Remove If Needed: If both conditions are true, return null to delete this node.
5. Return Node Otherwise: If not, return the current node.

This approach ensures that all "waves" of leaf removal are handled in a single bottom-up traversal, making it efficient and elegant. No additional data structures are needed, and we modify the tree in-place.

Example Walkthrough

Let's use the following tree as an example, with target = 2:

        1
       / \
      2   3
         / \
        2   4
  

Step-by-step:

1. First, process the left child of root (node 2). It's a leaf and its value is 2 (the target), so it's removed.
2. Next, process the right child of root (node 3). Its left child is 2 (a leaf), so it's removed. Its right child is 4 (a leaf, not target), so it stays.
3. Now, node 3 has only one child (4), so it is not a leaf and not removed.
4. The root node (1) now has left = null and right = node 3.
5. No more leaves with value 2 remain, so the process is complete.

Final tree:

        1
         \
          3
           \
            4
  

Time and Space Complexity

• Brute-force approach: If you repeatedly traverse the tree and remove leaves with the target value, each traversal is O(N) and you might need up to O(N) traversals, leading to O(N^2) time complexity.
• Optimized (recursive) approach: Each node is visited once in a post-order traversal, so the time complexity is O(N), where N is the number of nodes in the tree.
• Space complexity: The space used is O(H), where H is the height of the tree, due to the recursion stack. In the worst case (unbalanced tree), H = N; in the best case (balanced tree), H = log N.

Summary

The key insight to this problem is recognizing that removing leaves can create new leaves, so a bottom-up (post-order) approach is essential. By processing children before their parent, we ensure that all necessary nodes are considered for removal in a single traversal. The recursive solution is efficient, elegant, and easy to implement, making use of the natural structure of binary trees and recursion.