1325. Delete Leaves With a Given Value

Problem Description

In this problem, we're given a binary tree where each node contains an integer value. Our task is to remove all the leaf nodes that have a value equal to a given target integer. A leaf node is defined as a node that doesn't have left or right children. However, this operation has a cascade effect: if, after removing a leaf node, its parent node becomes a leaf node and its value is equal to the target, then we should also remove that parent node. We need to continue this process recursively until there are no more nodes that meet the criteria for deletion.

In summary, we're tasked with pruning the binary tree by removing target-valued leaf nodes and continuing to remove their respective parent nodes if they become target-valued leaves as a result.

Intuition

To solve this problem effectively, we can make use of recursion, which lends itself naturally to trees' hierarchical structure. The intuition is as follows: we will perform a post-order traversal of the tree. This means that we will first look at the child nodes before dealing with their parent nodes. This ordering is crucial because it allows us to decide whether the parent should be deleted after we've already considered and possibly deleted its children.

Here is a step-by-step process of the recursive solution:

1. If the current node is None (or in other words, if we're looking at an empty spot in the tree), we simply return None, as there is nothing to delete.
2. We recursively call the function on the left child of the current node. This will prune the left subtree and return the new left child for the current node.
3. We do the same for the right child of the current node.
4. After we have the results of the recursive calls for both children, we check the current node's value. If the current node has no children left (both are None after the recursive calls) and its value is equal to target, we will return None. This effectively deletes the current node because when the recursion rolls back up to the parent, this node will not be reattached to the tree.
5. If the current node isn't a leaf or its value doesn't match target, we return the current node itself, potentially with modified children, resulting from the recursive deletion process.

By following this approach, we can ensure that all nodes that are or become leaf nodes with value target are removed from the tree.

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

Solution Approach

The implementation of the solution uses a basic pattern of tree traversal called post-order traversal. This approach processes a node's children before the node itself, which is ideal for this problem since we need to look at the leaf nodes before making decisions about their parents.

Here's a detailed explanation of the algorithms, data structures, or patterns used in the solution:

1. Recursive Function: The solution defines a recursive function removeLeafNodes that takes a TreeNode root and an integer target as input. The base case of this recursive function is when the root is None. If this is the case, we return None because there's nothing to do on an empty subtree.

2. Post-order Traversal: The function calls itself to handle the left and right subtrees root.left = self.removeLeafNodes(root.left, target) and root.right = self.removeLeafNodes(root.right, target). These recursive calls will first prune the subtrees before looking at the current node. This is the essence of post-order traversal—visit left, then right, then process the node.

3. Leaf Node Check and Deletion: After the recursive calls, the function checks whether the current node is now a leaf node if root.left is None and root.right is None. If it's a leaf node and its value equals the target and root.val == target, we return None to delete this node.

4. Returning Pruned Tree: If the current node is not a target leaf node, it simply returns the current node return root. This might be a node with one or both children pruned, or it might be unchanged if neither child was a target leaf.

Here's what the main parts of the function look like in code:

• Recursive call to traverse and prune the left subtree:

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

• Recursive call to traverse and prune the right subtree:

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

• Checking if the current node is a leaf and should be deleted:

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

• Returning the node if it shouldn't be pruned:

  1return root

By combining these steps, the solution prunes the tree in one pass by leveraging the call stack inherent in recursion, allowing us to visit nodes in the precise order necessary to solve the problem efficiently.

Example Walkthrough

Let's demonstrate how the solution approach works with the following small example:

Suppose we have a binary tree where the target value we want to remove is 1. The initial tree looks like this:

1    1
2   / \
3  2   1
4 /   / \
52   1   2
6   /
7  1

Following the solution approach, here's what happens step-by-step:

1. Start with the root node with the value 1.
2. Recursively traverse to the left child which has a value of 2.
   1. Since the left child of 2 is also 2, recur on it.
      • It's a leaf and not equal to our target 1, so it will not be pruned and is returned as is.
   2. The right child of the first 2 is None, so no action is needed.
   3. Check the first 2, it's not a leaf node because it still has a left child, so it's also returned as is.
3. Recursively traverse to the right child of the root which has a value of 1.
   1. The left child of this 1 is another 1.
      • It has a leaf 1 as a left child, which is equal to our target and thus pruned and returned as None.
      • The right child is None, so after pruning its left child, this 1 has become a leaf itself and since its value is the target, it is pruned too and returned as None.
   2. The right child of the first 1 on the right side has a value of 2, which is a leaf but not equal to our target, so it remains as is.
4. Now, the root node has its left subtree unchanged and right subtree modified (as the 1 has been pruned). The right subtree is now:

   11
   2 \
   3  2

5. The root 1 is not a leaf, so it stays. The final pruned tree looks like:

1    1
2   / \
3  2   1
4 /     \
52       2

By following the post-order traversal, we efficiently pruned all leaves with the target value 1 and also those becoming leaves after pruning their children, with one sweep of recursion.

Solution Implementation

Time and Space Complexity

Time Complexity

The given code visits each node of the binary tree exactly once. The operations performed per node (checking if a node is a leaf and whether it carries the target value) are constant time operations. Therefore, the time complexity is O(N), where N is the number of nodes in the tree.

Space Complexity

The space complexity is affected by the recursive calls to removeLeafNodes. In the worst case, the tree could be skewed, meaning each level contains a single node. In this case, there would be O(N) recursive calls on the call stack at the same time. Therefore, the worst-case space complexity is O(N). However, in the average case, where the tree is balanced, the height of the tree would be O(log N), leading to a space complexity of O(log N) due to the call stack.

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