Problem Description

You are given a binary tree and an integer target. Your task is to delete all leaf nodes that have a value equal to target.

The key challenge is that this deletion process should be recursive in nature. When you delete a leaf node with value target, its parent node might become a new leaf node. If this newly created leaf node also has value target, it should be deleted as well. This process continues until no more leaf nodes with value target can be deleted.

For example, consider a tree where a parent node has value target and two children that are both leaf nodes with value target. First, you would delete both children. After deleting them, the parent becomes a leaf node. Since the parent also has value target and is now a leaf, it should be deleted too.

The function should return the root of the modified tree after all possible deletions. If the entire tree gets deleted (including the root), the function should return None.

A leaf node is defined as a node that has no left child and no right child.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: A binary tree is a special type of graph where each node has at most two children and there are no cycles.

Is it a tree?

• Yes: The problem explicitly states we're working with a binary tree structure.

DFS

• Yes: We arrive at DFS (Depth-First Search) as our algorithm choice.

Conclusion: The flowchart suggests using a DFS approach for this problem. This makes perfect sense because:

1. We need to traverse the entire tree to identify and remove leaf nodes with the target value
2. The deletion process needs to work from the bottom up - we must first process children before determining if a parent becomes a leaf node
3. DFS naturally processes nodes in a post-order fashion (left subtree → right subtree → current node), which is exactly what we need for this cascading deletion problem
4. After processing both children of a node, we can determine if that node itself has become a leaf and should be deleted

The DFS pattern allows us to recursively visit each node, process its children first, and then make decisions about the current node based on the updated state of its children. This bottom-up approach ensures that we correctly handle the cascading nature of the deletions where removing leaves can create new leaves that also need to be removed.

Intuition

The key insight for solving this problem is recognizing that we need to work from the bottom of the tree upward. Why? Because deleting leaf nodes can cause their parents to become new leaf nodes, which might also need deletion.

Think about it this way: if we tried to delete nodes from top to bottom, we wouldn't know whether a parent node will become a leaf until after we've processed its children. This creates a dependency - we can't make a decision about a parent until we know what happens to its children.

This naturally leads us to a post-order traversal pattern where we:

1. First process the left subtree completely
2. Then process the right subtree completely
3. Finally make a decision about the current node

By the time we reach a node, both its subtrees have been fully processed and cleaned up. At this point, we can check: "Is this node now a leaf (both children are None)? And does it have the target value?" If yes, we return None to effectively delete it. Otherwise, we keep the node.

The recursive nature of DFS perfectly captures this bottom-up processing. Each recursive call handles a subtree and returns either the modified subtree or None if the entire subtree should be deleted. The parent then uses these returned values to update its children pointers.

The beauty of this approach is that it handles the cascading deletions automatically. When a node's children are deleted (returning None), that node immediately knows it's now a leaf and can check if it should also be deleted. This ripple effect continues up the tree until we reach nodes that either don't have the target value or aren't leaves after cleanup.

Learn more about Tree, Depth-First Search and Binary Tree patterns.

Solution Approach

The implementation uses a recursive DFS approach with post-order traversal. Let's walk through how the solution works:

Base Case:

if root is None:
    return None

If we encounter a None node (empty subtree), we simply return None. This handles the case where we've reached beyond leaf nodes.

Recursive Processing:

root.left = self.removeLeafNodes(root.left, target)
root.right = self.removeLeafNodes(root.right, target)

These two lines are the heart of the post-order traversal. We first recursively process the left subtree, then the right subtree. The key insight here is that we're not just traversing - we're also updating the child pointers. If a subtree gets completely deleted (returns None), the parent's pointer to that child becomes None.

Decision Logic:

if root.left is None and root.right is None and root.val == target:
    return None
return root

After processing both children, we check if the current node should be deleted. A node is deleted if:

• It has no left child (root.left is None)
• It has no right child (root.right is None)
• Its value equals the target (root.val == target)

If all three conditions are met, we return None to signal this node should be deleted. Otherwise, we return the node itself.

How Cascading Deletion Works:

Consider a small example where node A (value = target) has two children B and C (both leaves with value = target):

1. When we process node A, we first recursively process B
2. B is a leaf with target value, so it returns None
3. We then process C, which also returns None
4. Now root.left and root.right for A are both None
5. A is now a leaf! If A's value equals target, it also returns None

The algorithm elegantly handles the cascading nature by updating parent-child relationships as it unwinds the recursion stack. Each level of recursion makes its deletion decision based on the already-processed results from deeper levels.

Time Complexity: O(n) where n is the number of nodes, as we visit each node exactly once.

Space Complexity: O(h) where h is the height of the tree, due to the recursion call stack.

Example Walkthrough

Let's walk through a concrete example to see how the algorithm works. Consider this binary tree where we want to delete all leaf nodes with target = 2:

Initial Tree:
      1
     / \
    2   2
   /   
  2    

Target: 2

Step-by-step execution:

1. Start at root (value=1)

• First, recursively process left child (value=2)

2. Process left subtree rooted at node (value=2)

• Recursively process its left child (value=2, leaf)
• Since this is a leaf with value=2, return None
• Recursively process its right child (doesn't exist, returns None)
• After processing: left=None, right=None
• This node is now a leaf with value=2, so return None

3. Back at root (value=1)

• Left subtree processing complete, root.left becomes None
• Now recursively process right child (value=2)

4. Process right subtree rooted at node (value=2)

• Left child doesn't exist (returns None)
• Right child doesn't exist (returns None)
• This is a leaf with value=2, so return None

5. Back at root (value=1) again

• Right subtree processing complete, root.right becomes None
• Check if root should be deleted:
  • Is it a leaf? Yes (both children are None)
  • Does it have target value? No (1 ≠ 2)
• Return the root node

Final Tree:

  1

The algorithm successfully deleted all nodes with value 2. Notice how the deletion of the leftmost leaf (2) caused its parent (also 2) to become a leaf, which was then deleted in the cascading manner. The root survived because although it became a leaf, its value (1) didn't match the target.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the number of nodes in the binary tree. The algorithm performs a post-order traversal of the tree, visiting each node exactly once. At each node, it performs constant time operations (checking if it's a leaf node and comparing its value with the target), so the overall time complexity is linear with respect to the number of nodes.

Space Complexity: O(h) where h is the height of the binary tree. The space complexity is determined by the recursive call stack. In the worst case of a skewed tree (essentially a linked list), the height would be n, making the space complexity O(n). In the best case of a perfectly balanced tree, the height would be log(n), making the space complexity O(log n). The algorithm doesn't use any additional data structures besides the implicit call stack for recursion.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Attempting Pre-order or In-order Traversal

The Problem: A common mistake is trying to solve this problem using pre-order traversal (processing the current node before its children). This approach fails because you might delete a leaf node before realizing its parent should also be deleted.

Incorrect Approach:

def removeLeafNodes(self, root, target):
    if root is None:
        return None
  
    # WRONG: Checking current node first
    if root.left is None and root.right is None and root.val == target:
        return None
  
    # Processing children after parent - won't catch cascading deletions
    root.left = self.removeLeafNodes(root.left, target)
    root.right = self.removeLeafNodes(root.right, target)
  
    return root

This fails because when you check if a node is a leaf, its children haven't been processed yet. A node that appears to have children initially might become a leaf after those children are deleted.

Solution: Always use post-order traversal - process children first, then make decisions about the current node based on the updated state.

Pitfall 2: Not Updating Parent Pointers

The Problem: Some implementations correctly identify which nodes should be deleted but forget to update the parent's pointers to the deleted children.

Incorrect Approach:

def removeLeafNodes(self, root, target):
    if root is None:
        return None
  
    # WRONG: Just calling recursively without updating pointers
    self.removeLeafNodes(root.left, target)
    self.removeLeafNodes(root.right, target)
  
    if root.left is None and root.right is None and root.val == target:
        return None
  
    return root

Solution: Always assign the return value of recursive calls back to the child pointers:

root.left = self.removeLeafNodes(root.left, target)
root.right = self.removeLeafNodes(root.right, target)

Pitfall 3: Checking Original Children State Instead of Updated State

The Problem: Storing references to children before recursion and using those stored references for the leaf check.

Incorrect Approach:

def removeLeafNodes(self, root, target):
    if root is None:
        return None
  
    # WRONG: Storing original children
    left_child = root.left
    right_child = root.right
  
    root.left = self.removeLeafNodes(root.left, target)
    root.right = self.removeLeafNodes(root.right, target)
  
    # WRONG: Using original children for leaf check
    if left_child is None and right_child is None and root.val == target:
        return None
  
    return root

This incorrectly uses the original state of children to determine if the node is a leaf, missing cases where the node becomes a leaf after children are deleted.

Solution: Always check the current state of root.left and root.right after the recursive calls have updated them.