medium Delete Leaves With a Given Value

Problem Statement

Given a root node of a binary tree and an integer target, delete all leaf nodes that have a value equal to target.

After removing such leaf nodes, if any of their parent nodes become leaf nodes with a value equal to target, they should also be removed. This process should continue until no more nodes can be deleted.

Examples

Example 1

• Input: root = [1, 5, 3, 5, null, 5, 4], Target: 5

• Expected Output: [1,null,3,null,4]
• Explanation: The left child of 5 (left of root) is 3 and 5. When we remove both leaf having value 5, the left node of the root also becomes a leaf having a value equal to 5. So, we also remove it.

Example 2

• Input: root = [3, 3, 3, 3, 3, null, 4], Target: 3

• Expected Output: [3,null,3,null,4]
• Explanation: Remove all 3 except the root and right child of the root node.

Example 3

• Input: root = [4, 5, 6, 5, null, 7, 8], Target: 5

• Expected Output: [4,null,6,7,8]
• Explanation: The leaf nodes with value 5 are removed first. The tree becomes [4, 5, 6, null, null, 7, 8]. Now, again remove the leaf node with the value 5 and the tree becomes [4, null, 6, 7, 8]`.

Constraints:

• The number of nodes in the tree is in the range [1, 3000].
• 1 <= Node.val, target <= 1000

Solution

To solve this problem, we use a recursive depth-first search (DFS) approach. We start from the root of the tree and recursively process the left and right subtrees to remove all leaf nodes with the given target value. During each recursive call, if a node becomes a leaf and its value matches the target, we remove it by returning null. This process continues until no target leaf nodes remain in the tree, ensuring that all eligible nodes are removed even if their parent nodes later become leaf nodes with the target value.

Step-by-Step Algorithm

1. Check if the Current Node is Null:

   • If root is null, return null. This handles cases where the tree or subtree is empty.

2. Recursively Process the Left Subtree:

   • Call removeLeafNodes(root.left, target) to remove target leaf nodes from the left subtree.
   • Update root.left with the returned value.

3. Recursively Process the Right Subtree:

   • Call removeLeafNodes(root.right, target) to remove target leaf nodes from the right subtree.
   • Update root.right with the returned value.

4. Check if the Current Node is a Target Leaf:

   • If root.left and root.right are both null and root.val equals the target, it means the current node is a target leaf node.
   • Return null to remove the current node if it matches the target value and is a leaf.

5. Return the Updated Node:

   • If the current node is not a target leaf, return root to retain the node in the updated tree.

Step-by-Step Algorithm Walkthrough

Given the input:

• Tree: [1, 5, 3, 5, null, 5, 4]
• Target: 5

1. Start at the Root Node 1:

   • root is 1, call removeLeafNodes on root.left (node 5).

2. Process Left Child 5 of Root 1:

   • root is 5, call removeLeafNodes on root.left (node 5).

3. Process Left Child 5 of Node 5:

   • It is leaf node and value is equal to target(5). So, return null.

4. Return to Node 5 (Left Child of Root 1):

   • root.left is null.
   • Call removeLeafNodes on root.right (null) — returns null.
   • root is a target leaf (val = 5), return null.

5. Return to Root Node 1:

   • root.left is updated to null.
   • Call removeLeafNodes on root.right (node 3).

6. Process Right Child 3 of Root 1:

   • root is 3, call removeLeafNodes on root.left (node 5).

7. Process Left Child 5 of Node 3:

   • It is leaf node and value is equal to target(5). So, return null.

8. Return to Node 3:

   • root.left is null.
   • Call removeLeafNodes on root.right (node 4) — returns node 4.

9. Complete Processing Node 3:

   • root.right is 4, not a target leaf, so return 3.

10. Finish at Root Node 1:

    • root.left is null and root.right is 3. Return 1 as the final root.

Resulting tree after removal is: [1, null, 3, null, 4].

Code

import java.util.LinkedList;
import java.util.Queue;

// class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;

//     TreeNode(int val) {
//         this.val = val;
//     }
// }

class Solution {

  public TreeNode removeLeafNodes(TreeNode root, int target) {
    if (root == null) return null; // If the tree is empty, return null

    // Recursively remove leaf nodes from the left and right subtrees
    root.left = removeLeafNodes(root.left, target);
    root.right = removeLeafNodes(root.right, target);

    // Check if the current node becomes a leaf node with target value
    if (root.left == null && root.right == null && root.val == target) {
      return null; // Remove the node by returning null
    }
    return root;
  }

  public void printTree(TreeNode root) {
    if (root == null) {
      System.out.println("Tree is empty");
      return;
    }

    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);

    while (!queue.isEmpty()) {
      int levelSize = queue.size();
      boolean hasNextLevel = false; // Flag to check if the next level has nodes
      LinkedList<String> currentLevel = new LinkedList<>(); // To store nodes of the current level

      for (int i = 0; i < levelSize; i++) {
        TreeNode current = queue.poll();

        if (current != null) {
          currentLevel.add(String.valueOf(current.val));
          // If there are children, add them to the queue
          queue.add(current.left);
          queue.add(current.right);

          // If there are any non-null children, set the flag to true
          if (current.left != null || current.right != null) {
            hasNextLevel = true;
          }
        } else {
          currentLevel.add("null");
        }
      }

      // Print the current level, excluding trailing nulls
      while (
        !currentLevel.isEmpty() && currentLevel.peekLast().equals("null")
      ) {
        currentLevel.pollLast();
      }

      for (String node : currentLevel) {
        System.out.print(node + " ");
      }

      // Stop processing if no next level exists
      if (!hasNextLevel) {
        break;
      }
    }
    System.out.println();
  }

  public static void main(String[] args) {
    // Example 1
    TreeNode root1 = new TreeNode(1);
    root1.left = new TreeNode(5);
    root1.right = new TreeNode(3);
    root1.left.left = new TreeNode(5);
    root1.right.left = new TreeNode(5);
    root1.right.right = new TreeNode(4);
    int target1 = 5;

    Solution solution = new Solution();
    TreeNode newRoot1 = solution.removeLeafNodes(root1, target1);
    System.out.print("After removing leaf nodes: ");
    solution.printTree(newRoot1);
  }
}

Complexity Analysis

Time Complexity

The algorithm uses a depth-first search (DFS) to traverse the binary tree. In the worst case, the DFS will visit every node in the tree once. Thus, the time complexity is , where n is the total number of nodes in the binary tree.

Space Complexity

The space complexity is determined by the maximum depth of the recursion stack, which corresponds to the height of the binary tree. In the worst case, the height of the tree could be for a skewed tree (where every node has only one child), resulting in a space complexity of .