We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Delete Leaves With a Given Value

Number: 1450

Difficulty: Medium

Paid? No

Companies: Google, Amazon, Microsoft

Problem Description

Given a binary tree root and an integer target, delete all the leaf nodes with value target. Note that once a leaf node is deleted, its parent node may become a leaf with the same target value and should also be deleted. Continue this process until no such leaf nodes remain.

Key Insights

  • Use a recursive postorder traversal (process children before the current node).
  • After processing the subtrees, check if the current node is a leaf with the target value.
  • Removing a leaf might cause its parent to become a new leaf with the target, requiring further deletion.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the tree, as each node is visited once. Space Complexity: O(h), where h is the height of the tree, due to recursion stack usage.

Solution

The solution employs a postorder DFS approach. This ensures that both the left and right subtrees are processed completely before evaluating the parent node. As soon as the helper function processes and updates the left and right children recursively, it checks if the current node has become a leaf that matches the target. If it does, the function returns null to effectively remove the node from the tree. This method naturally handles the cascading deletion of nodes that become eligible as new leaves with the target value.

Code Solutions

# 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:
        # Base case: return None if the node is null.
        if not root:
            return None
        
        # Recursively process the left and right children.
        root.left = self.removeLeafNodes(root.left, target)
        root.right = self.removeLeafNodes(root.right, target)
        
        # Check if the current node is a leaf and equals the target.
        if not root.left and not root.right and root.val == target:
            return None
        
        # Return the updated node.
        return root
← Back to All Questions