Delete Leaves With a Given Value

Problem Description

Given a binary tree root and an integer target, delete all the leaf nodes with value target.

Note that after deleting 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).

Examples

Constraints

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

Bottom-Up Postorder Pruning

Because deleting a child can turn its parent into a leaf node, we must check children before parents. This requires postorder DFS traversal. We write a recursive function removeLeafNodes(node, target):

1. If the node is null, return null.
2. Recursively prune the left subtree: node.left = removeLeafNodes(node.left, target).
3. Recursively prune the right subtree: node.right = removeLeafNodes(node.right, target).
4. After resolving both subtrees, check if the current node has become a leaf node (node.left == null && node.right == null) and matches our target.
   • If it is, return null to prune this node.
   • Otherwise, return node to preserve it.

Solution 1: Postorder Leaf Pruning

Prune children subtrees first, then check if parent has become a leaf that matches the target.

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

        // Prune children first
        root.left = removeLeafNodes(root.left, target);
        root.right = removeLeafNodes(root.right, target);

        // If current node is now a leaf and matches target, prune it
        if (root.left == null && root.right == null && root.val == target) {
            return null;
        }
        return root;
    }
}

# 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 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() : 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) {
            delete root; // prevent memory leaks in C++
            return nullptr;
        }
        return root;
    }
};

Complexity Analysis

• Time Complexity: O(n) since we visit every node in the binary tree exactly once.
• Space Complexity: O(h) auxiliary space where h is the tree height, representing the recursion stack depth.

← All Problems