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.

Flowchart Walkthrough

To determine the suitable algorithm for solving LeetCode problem 1325 (Delete Leaves With a Given Value), we will use the guiding questions from the Flowchart. Here’s the analysis step-by-step:

Is it a graph?

Yes: A binary tree is a specialized form of a graph.

Is it a tree?

Yes: The problem specifically deals with a binary tree.

As the problem directly deals with a tree and involves traversing in a manner that may require revisiting nodes based on the deletion condition (value comparison), the Depth-First Search (DFS) pattern is suitable. This method helps efficiently handle recursive traversal and modification of the tree nodes, particularly for operations involving conditions on the leaf nodes.

Conclusion: The flowchart analysis indicates that DFS is the appropriate technique for handling problems involving conditions on trees, as in this problem where specific leaf nodes need to be identified and potentially deleted based on their values.

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:

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.
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.
We do the same for the right child of the current node.
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.
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:

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.
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.
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.
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:

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

Recursive call to traverse and prune the right subtree:

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

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

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

Returning the node if it shouldn't be pruned:
```
return 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.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

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:

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

Start with the root node with the value 1.
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.
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.
Now, the root node has its left subtree unchanged and right subtree modified (as the 1 has been pruned). The right subtree is now:
```
1
 \
  2
```
The root 1 is not a leaf, so it stays. The final pruned tree looks like:

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

1# Definition for a binary tree node.
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val         # Node's value
5        self.left = left       # Node's left child
6        self.right = right     # Node's right child
7
8class Solution:
9    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:
10        """
11        Recursively removes all leaf nodes from the binary tree that have the given target value.
12
13        Parameters:
14        root (TreeNode): The root of the binary tree.
15        target (int): The target value for which leaf nodes should be removed.
16
17        Returns:
18        TreeNode: The root of the modified binary tree after removing the target leaf nodes.
19        """
20        # Return None if the current node is None
21        if root is None:
22            return None
23      
24        # Recursively remove target leaf nodes from the left subtree
25        root.left = self.removeLeafNodes(root.left, target)
26      
27        # Recursively remove target leaf nodes from the right subtree
28        root.right = self.removeLeafNodes(root.right, target)
29      
30        # If the current node is a leaf and its value matches the target, 
31        # return None to remove it
32        if root.left is None and root.right is None and root.val == target:
33            return None
34      
35        # Return the current node if it is not a target leaf node
36        return root
37

1// Definition for a binary tree node.
2class TreeNode {
3    int val; // Value of the node
4    TreeNode left; // Reference to the left child node
5    TreeNode right; // Reference to the right child node
6  
7    // Constructor to initialize the node with no children
8    TreeNode() {}
9  
10    // Constructor to initialize the node with a value
11    TreeNode(int val) { this.val = val; }
12  
13    // Constructor to initialize the node with a value and references to left and right children
14    TreeNode(int val, TreeNode left, TreeNode right) {
15        this.val = val;
16        this.left = left;
17        this.right = right;
18    }
19}
20
21class Solution {
22    // Removes all leaf nodes with a specified value from a binary tree.
23    public TreeNode removeLeafNodes(TreeNode root, int target) {
24        // If the root is null, the tree is empty, and we return null as there are no nodes to remove.
25        if (root == null) {
26            return null;
27        }
28      
29        // Recursively remove leaf nodes from the left subtree.
30        root.left = removeLeafNodes(root.left, target);
31        // Recursively remove leaf nodes from the right subtree.
32        root.right = removeLeafNodes(root.right, target);
33      
34        // Check if the current node is a leaf node with the target value.
35        if (root.left == null && root.right == null && root.val == target) {
36            // If so, remove this node by returning null to the parent call.
37            return null;
38        }
39      
40        // Return the possibly updated root to the previous recursive call.
41        // If no changes were made, the original node is returned.
42        return root;
43    }
44}
45

1#include <cstddef> // for nullptr
2
3// Forward declaration for the TreeNode struct.
4struct TreeNode {
5    int val; // Value of the node.
6    TreeNode *left; // Pointer to the left child node.
7    TreeNode *right; // Pointer to the right child node.
8  
9    // Constructor for a tree node with a default value of 0 and no children.
10    TreeNode() : val(0), left(nullptr), right(nullptr) {}
11
12    // Constructor for creating a leaf node with a specific value.
13    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
14
15    // Constructor for creating a node with specific value and left/right children.
16    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
17};
18
19class Solution {
20public:
21    // Function to remove all leaf nodes in a binary tree that have the specified target value.
22    TreeNode* removeLeafNodes(TreeNode* node, int target) {
23        // If the current node is null, we have reached the end of a branch and return null.
24        if (!node) {
25            return nullptr;
26        }
27      
28        // Recursively remove target leaves from the left subtree.
29        node->left = removeLeafNodes(node->left, target);
30      
31        // Recursively remove target leaves from the right subtree.
32        node->right = removeLeafNodes(node->right, target);
33      
34        // If the current node is a leaf (has no children) and its value equals the target,
35        // delete this node by returning null.
36        if (!node->left && !node->right && node->val == target) {
37            delete node; // Free the memory of the node to avoid memory leaks.
38            return nullptr;
39        }
40
41        // Return the potentially updated current node.
42        return node;
43    }
44};
45

1// Definition for a binary tree node.
2class TreeNode {
3  val: number;
4  left: TreeNode | null;
5  right: TreeNode | null;
6
7  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
8    this.val = val === undefined ? 0 : val; // Assign the given value, or default to 0 if no value is provided.
9    this.left = left === undefined ? null : left; // Assign the given left child, or default to null if none.
10    this.right = right === undefined ? null : right; // Assign the given right child, or default to null if none.
11  }
12}
13
14/**
15 * Removes all leaf nodes with the specified target value from the binary tree.
16 * If, after removing a leaf, the parent also becomes a leaf with the target value, it gets removed as well, and so on.
17 * @param {TreeNode | null} node - The current node of the binary tree.
18 * @param {number} target - The value of the target leaf nodes that need to be removed.
19 * @return {TreeNode | null} The modified tree with specified leaf nodes removed.
20 */
21function removeLeafNodes(node: TreeNode | null, target: number): TreeNode | null {
22  // Base case: if the current node is null, simply return null.
23  if (!node) {
24    return null;
25  }
26
27  // Recursively remove leaf nodes in the left subtree.
28  node.left = removeLeafNodes(node.left, target);
29  // Recursively remove leaf nodes in the right subtree.
30  node.right = removeLeafNodes(node.right, target);
31
32  // Check if the current node has become a leaf node with the value equal to target.
33  // If so, remove this node by returning null; otherwise, return the current node.
34  if (node.left === null && node.right === null && node.val === target) {
35    return null;
36  } else {
37    return node;
38  }
39}
40

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Linear Search

Binary Search

Quick Select

Hash Set

I don't know