Problem

Given a binary tree root and an integer target, delete all the leaf nodes with value target.

Note that once you delete a leaf node with value target, if its parent node becomes a leaf node and has the value target, it should also be deleted (you need to continue doing that until you cannot).

Examples

Example 1:

Input: root = [1,2,3,2,null,2,4], target = 2
Output: [1,null,3,null,4]
Explanation: Leaf nodes in green with value (target = 2) are removed (Picture in left). 
After removing, new nodes become leaf nodes with value (target = 2) (Picture in center).

Example 2:

Input: root = [1,3,3,3,2], target = 3
Output: [1,3,null,null,2]

Example 3:

Input: root = [1,2,null,2,null,2], target = 2
Output: [1]
Explanation: Leaf nodes in green with value (target = 2) are removed at each step.

Solution

Method 1 - Post-order traversal

As we see in example 3, We have initially one leaf nodes with target = 2. But as soon as we remove the leaf node, we get another leaf node with target = 2. So, the idea is simple - we need to process the leaf nodes first, and then the parents aka we have to do post order traversal.

Algorithm

  1. Remove target leaf node from children - say left first and then right
  2. Then, check if parent is leaf because of removal, and is equal to target, then process parent as well
  3. Repeat step 1 and 2, till our traversal is complete

Video explanation

Here is the video explaining this method in detail. Please check it out:

Code

Java
public TreeNode removeLeafNodes(TreeNode root, int target) {
	if(root == null) {
		return root;
	}
	
	root.left = removeLeafNodes(root.left, target);
	root.right = removeLeafNodes(root.right, target);
	if(root.left == null && root.right == null && root.val == target){
		return null;
	}
	
	return root;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n) (assuming we count space in recursive stack, otherwise O(1).