#1325

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Delete Leaves With a Given Value

In this problem, you need to delete all leaf nodes in a binary tree with a given target value, performing continuous deletion on affected nodes.

tree depth first search binary tree

Problem Statement

You are given the root of a binary tree and an integer target. Your task is to delete all the leaf nodes in the tree that have the given target value. If, after deleting a leaf, its parent becomes a leaf and also has the target value, continue deleting the parent node until no more deletions can be made.

The binary tree will be represented in an array, and the target value is also provided. You need to return the root of the tree after all the deletions are complete. If no leaf node matches the target, the tree remains unchanged.

Examples

Example 1

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

Output: [1,null,3,null,4]

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 details omitted.

Example 3

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

Output: [1]

Leaf nodes in green with value (target = 2) are removed at each step.

Constraints

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

Solution Approach

Depth-First Search (DFS) Traversal

The primary approach for this problem is to use DFS to traverse the tree, checking each node to determine if it is a leaf and if its value matches the target. If it does, the node should be removed. The DFS approach ensures that we examine each subtree and recursively delete the leaf nodes until no more deletions are possible.

State Tracking During Traversal

During the DFS traversal, you will track the state of nodes to ensure that when a node becomes a leaf, it is checked for the target value. If its value matches the target, it should be deleted, and the recursion continues to check its parent node. This ensures that the tree is modified correctly by maintaining state throughout the traversal.

Recursive Deletion and Tree Reconstruction

The recursion ensures that nodes are deleted one by one. After each deletion, the function reconstructs the tree by returning the root of the current subtree, and this process continues until all applicable leaves are removed. The recursive nature of the function helps in handling all potential edge cases.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

The time complexity is O(n) since each node is visited exactly once during the DFS traversal. The space complexity is O(n) because of the recursive stack used for DFS, where n is the number of nodes in the tree.

What Interviewers Usually Probe

Understanding of DFS and its application in tree-based problems.
Ability to manage tree reconstruction and state tracking through recursion.
Experience in dealing with binary trees and edge cases like consecutive deletions.

Common Pitfalls or Variants

Common pitfalls

Not properly handling the parent-child relationship after deletion, leading to missed deletions.
Failing to account for edge cases where multiple deletions affect the tree structure.
Incorrectly managing the recursive return values, which can result in incorrect tree reconstruction.

Follow-up variants

Modify the problem to remove nodes with any value instead of just leaf nodes.
Extend the problem to handle more complex tree structures with additional constraints.
Adjust the problem to return a list of deleted nodes instead of just the modified tree.

FAQ

How do I approach solving 'Delete Leaves With a Given Value'?

The problem can be tackled using DFS traversal, checking each node recursively and deleting leaves that match the target value. Once deleted, check if the parent becomes a leaf and continue deleting if necessary.

What is the time complexity of the 'Delete Leaves With a Given Value' problem?

The time complexity is O(n), where n is the number of nodes in the tree. Each node is visited exactly once during the DFS traversal.

How does recursion work in the solution for this problem?

Recursion helps in traversing the tree and ensuring that after each deletion, the parent node is checked if it becomes a leaf. The process continues until no deletions are left.

Can the tree be empty in the 'Delete Leaves With a Given Value' problem?

Yes, the tree can be empty, in which case the result is also an empty tree.

What if no leaf nodes have the target value in the 'Delete Leaves With a Given Value' problem?

If no leaf nodes match the target value, the tree will remain unchanged and be returned as-is.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def removeLeafNodes(
        self, root: Optional[TreeNode], target: int
    ) -> Optional[TreeNode]:
        if root is None:
            return None
        root.left = self.removeLeafNodes(root.left, target)
        root.right = self.removeLeafNodes(root.right, target)
        if root.left is None and root.right is None and root.val == target:
            return None
        return root

Continue Practicing

#1315 sum of nodes with even valued grandparent #1339 maximum product of splitted binary tree #1305 all elements in two binary search trees