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:

flowchart LR
    subgraph Tree1["Initial Tree"]
        A1(1)
        B1(2)
        C1(3)
        D1(2):::greenNode
        E1:::hidden
        F1(2):::greenNode
        G1(4)

        A1 --- B1
        A1 --- C1
        B1 --- D1
        B1 ~~~ E1
        C1 --- F1
        C1 --- G1
    end
    
    subgraph Tree2["After Step 1"]
        A2(1)
        B2(2):::greenNode
        C2(3)
        F2:::hidden
        G2(4)

        A2 --- B2 & C2
        C2 ~~~ F2
        C2 --- G2
    end
    
    subgraph Tree3["Final Tree"]
        A3(1)
        B3:::hidden
        C3(3)
        F3:::hidden
        G3(4)

        A3 ~~~ B3
        A3 --- C3
        C3 ~~~ F3
        C3 --- G3
    end
    
    Tree1 --- Tree2
    Tree2 --- Tree3

classDef hidden display:none
classDef greenNode fill:#A3CE9E,stroke:#2E8B57
  
1
2
3
4

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:

flowchart LR
    subgraph Tree1["Initial Tree"]
        A1(1)
        B1(3)
        C1(3):::greenNode
        D1(3):::greenNode
        E1(2)

        A1 --- B1
        A1 --- C1
        B1 --- D1
        B1 --- E1
    end

    subgraph Tree2["After Step 1"]
        A2(1)
        B2(3)
        E2(2)

        A2 --- B2
        A2 ~~~ C2:::hidden
        B2 ~~~ D2:::hidden
        B2 --- E2
    end

    Tree1 --- Tree2

classDef hidden display:none
classDef greenNode fill:#A3CE9E,stroke:#2E8B57
  
1
2

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

Example 3:

flowchart LR
    subgraph Tree1["Initial Tree"]
        A1(1)
        B1(2)
        C1:::hidden
        D1(2)
        E1:::hidden
        F1(2):::greenNode

        A1 --- B1
        A1 ~~~ C1
        B1 --- D1
        B1 ~~~ E1
        D1 --- F1
        D1 ~~~ G1:::hidden
    end

    subgraph Tree2["After Step 1"]
        A2(1)
        B2(2)
        C2:::hidden
        D2(2):::greenNode
        E2:::hidden
        F2:::hidden

        A2 --- B2
        A2 ~~~ C2
        B2 --- D2
        B2 ~~~ E2
    end

    subgraph Tree3["After Step 2"]
        A3(1)
        B3(2):::greenNode
        C3:::hidden

        A3 --- B3
        A3 ~~~ C3
    end
    
    subgraph Tree4["Final Tree"]
        A4(1)
    end

    Tree1 --- Tree2
	Tree2 --- Tree3
	Tree3 --- Tree4
	
classDef hidden display:none
classDef greenNode fill:#A3CE9E,stroke:#2E8B57
  
1
2
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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