Leetcode 1325. Delete Leaves With a Given Value

Problem Explanation

In this problem, we are given a binary tree and a target value. Our task is to remove all leaf nodes of the binary tree with values equal to the target. If after removing a leaf node, its parent becomes a leaf and its value is also equal to the target, the parent node needs to be removed as well. The process continues until there are no nodes that fit this criteria left.

For instance, consider the example where root = [1,2,3,2,null,2,4] and target = 2. Here, we would initially remove the leaf nodes with values equal to 2 (from left to right). After this, the parent of the removed nodes would become leaf nodes and if their values were 2 as well, we would remove them too. So the output after performing these operations would be [1,null,3,null,4].

Approach to the Solution

The problem can be solved using a simple depth-first search traversal of the binary tree. As we traverse the tree, we remove leaf nodes having the target value and return nullptr. Each time we remove a node, we will recursively check its children. If a node's children point to nullptr and its value equals the target, we will return nullptr for the node too, implying it has been removed. The depth-first search traversal will ensure that we traverse all nodes deeply before coming up and checking others. So, child nodes get preference to be deleted first and then we proceed to their parent.

Let's visualize this process with an example below:

Consider the input binary tree: [1,3,3,3,2] and target = 3

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

While traversing the tree, when we reach the leftmost leaf node 3, we see it equals our target and so we remove it by returning nullptr.

Then we backtrack to the parent node 3 which is a leaf node now and so we remove it as well and replace it with nullptr.

1
2
3           1
4         /  \
5      nullptr 3
6               \
7                2

Finally, we return to the root node, but it doesn't meet the removal condition and so we do nothing, giving our final tree which would be [1,3,null,null,2].

Solutions

Python Solution

1
2python
3class Solution:
4    def removeLeafNodes(self, root, target):
5
6        # base condition
7        if not root:
8            return None
9
10        # recursively removing child nodes
11        root.left = self.removeLeafNodes(root.left, target)
12        root.right = self.removeLeafNodes(root.right, target)
13
14        # if it's a leaf node and the node's value equals the target, remove the node
15        if root.left is None and root.right is None and root.val == target:
16            return None
17
18        return root

Java Solution

1
2java
3class Solution {
4    public TreeNode removeLeafNodes(TreeNode root, int target) {
5        if(root == null) return null; // Base condition
6
7        root.left = removeLeafNodes(root.left, target); // Recursive removal for left child
8        root.right = removeLeafNodes(root.right, target); // Recursive removal for right child
9
10        if(root.left == null && root.right == null && root.val == target) { // If leaf node with value equals the target.
11            return null;
12        }
13
14        return root;
15    }
16}

JavaScript Solution

1
2javascript
3var removeLeafNodes = function(root, target) {
4    if (!root) return null; // Base condition
5
6    root.left = removeLeafNodes(root.left, target); // Recursive removal for left child
7    root.right = removeLeafNodes(root.right, target); // Recursive removal for right child
8
9    if (root.left === null && root.right === null && root.val === target) { // If leaf node with value equals the target.
10        return null;
11    }
12
13    return root;
14}

C++ Solution

1
2cpp
3class Solution {
4public:
5    TreeNode* removeLeafNodes(TreeNode* root, int target) {
6        if (!root) return nullptr; // Base condition
7
8        root->left = removeLeafNodes(root->left, target); // Recursive removal for left child
9        root->right = removeLeafNodes(root->right, target); // Recursive removal for right child
10
11        if (!root->left && !root->right && root->val == target) { // If leaf node with value equals the target.
12            return nullptr;
13        }
14
15        return root;
16    }
17};

C# Solution

1
2csharp
3public class Solution {
4    public TreeNode RemoveLeafNodes(TreeNode root, int target) {
5        if (root == null) return null; // Base condition
6
7        root.left = RemoveLeafNodes(root.left, target); // Recursive removal for left child
8        root.right = RemoveLeafNodes(root.right, target); // Recursive removal for right child
9
10        if (root.left == null && root.right == null && root.val == target) { // If leaf node with value equals the target.
11            return null;
12        }
13
14        return root;
15    }
16}

Time Complexity

In all these solutions, the time complexity is O(n), where n is the number of nodes in the binary tree. This is because we are doing a DFS traversal and visiting each node exactly once.

Space Complexity

In terms of space complexity, it is O(h), where h is the height of the binary tree. This space is due to the recursive stack used during the DFS traversal.

Conclusion

Overall, this problem demonstrates how we can use recursive DFS traversal to solve the problem in a very neat and elegant manner. The key idea is to start from the bottom leaf and move upwards, deleting nodes if they qualify the criteria. This ensures that a parent only gets deleted if all its children are deleted, thereby preventing any inconsistencies from happening. The recursive deletion of nodes will automatically take care of all the necessary checks and balances. It is a great example of how recursion can simplify problems and processes in binary trees.