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
targetvalue to delete.
Outputs:
- The modified binary tree (root of the remaining structure). If all nodes are removed, return
None.
Implicit Constraints & Edge Cases:
- Empty Tree: Input might be an empty tree or a single node that matches target immediately.
- Cascade Deletion: A parent becomes a leaf only after children are processed. We cannot simply iterate once; we must process bottom-up (post-order).
- Duplicates: Nodes with
targetvalue 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:
- Recursively call the function on the left and right subtrees first. These calls return either a valid subtree root or
Noneif that branch was deleted entirely. - Update current node’s pointers to these returned values (
left,right). - Check the condition for deletion:
(node.left is None) AND (node.right is None)combined withnode.val == target. - If true, return
Nonefrom this level up the stack (effectively deleting the current node). - 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 roothandles an empty input immediately returningNone. - 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.leftandroot.rightimmediately 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.