Domain 2MediumMEDIUM

Delete Leaves With a Given Value

Use post-order DFS to recursively prune leaf nodes matching target, cascading deletions up.

Domain: medium•Updated: 2026-09-14
#post-order traversal#binary tree#O(N)#recursion

Problem Breakdown

We are given the root of a binary tree and an integer target. The goal is to remove all leaf nodes that have this specific value. Crucially, removing a node might change its parent’s status: if we delete both children (or one child was already gone), the current node becomes a new leaf. If that new leaf also matches the target, it must be deleted as well. This process repeats recursively until no more deletions are possible.

Inputs:

  • Binary tree root (TreeNode)
  • Integer target value to delete.

Outputs:

  • The modified binary tree (root of the remaining structure). If all nodes are removed, return None.

Implicit Constraints & Edge Cases:

  1. Empty Tree: Input might be an empty tree or a single node that matches target immediately.
  2. Cascade Deletion: A parent becomes a leaf only after children are processed. We cannot simply iterate once; we must process bottom-up (post-order).
  3. Duplicates: Nodes with target value deep in the tree might not be leaves initially but become so later.

Intuition

A naive approach would be to scan for all current leaves, remove them, then repeat until no changes occur. This is inefficient because we traverse the entire tree multiple times (O(N^2) worst case).

The key insight is that whether a node should be deleted depends entirely on its children’s state after they have been processed. If both left and right subtrees are effectively “gone” (either null or removed), then this current node becomes a leaf. We only delete it if node.val == target. This dependency structure screams Post-Order Traversal (process children before parent).

Approach

We will use Depth First Search (DFS) recursively:

  1. Recursively call the function on the left and right subtrees first. These calls return either a valid subtree root or None if that branch was deleted entirely.
  2. Update current node’s pointers to these returned values (left, right).
  3. Check the condition for deletion: (node.left is None) AND (node.right is None) combined with node.val == target.
  4. If true, return None from this level up the stack (effectively deleting the current node).
  5. Otherwise, return the current node as it remains part of the tree.

Complexity Analysis

  • Time: O(N), where N is the number of nodes in the binary tree. We visit every node exactly once during the traversal.
  • Space: O(H) for recursion stack space, where H is the height of the tree. In a skewed tree (worst case), this degrades to O(N). For balanced trees, it is O(log N).

Solution

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def removeLeafNodes(root: 'TreeNode', target: int) -> 'TreeNode':
    # Base case: if the tree is empty or we reach a deleted branch (None), return None.
    if not root:
        return None
    
    # Recursively process children first to determine their final state.
    left = removeLeafNodes(root.left, target)
    right = removeLeafNodes(root.right, target)
    
    # Update current node's pointers with the results from recursion.
    root.left = left
    root.right = right
    
    # Check if this node has become a leaf and matches the target value.
    # A node is considered deleted (returns None to parent) if:
    # 1. It currently has no children (both are None after recursive calls).
    # 2. Its value equals the target.
    if not root.left and not root.right and root.val == target:
        return None
    
    # Otherwise, keep this node in the tree.
    return root

Edge Cases Handled

  • Empty Input: The base case if not root handles an empty input immediately returning None.
  • All Nodes Match Target: If every node has value equal to target and is a leaf, each recursive call returns None, eventually bubbling up the deletion of the entire tree.
  • Parent Becomes Leaf After Child Removal: The logic updates root.left and root.right immediately after recursion. This ensures that if a child was removed (returned None), we correctly evaluate whether the parent has become a leaf in this specific step before deciding to delete it.