Delete Leaves With a Given Value

Medium

Google

1 view

Topics:

TreesRecursion

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

For example:

Consider the following binary tree:

If target = 2, the algorithm should proceed as follows:

Initially, the leaf nodes with value 2 are removed:

    1
   / \
  _   3
 / \ / \
_  4 _  _

After removing the initial leaves, the nodes with value 2 which became leaf nodes are removed:

Consider the following binary tree:

    1
   / \
  3   3
 / \ / \
3  2 _  _

If target = 3, the algorithm should return:

Write a function that takes the root of a binary tree and a target value as input and returns the modified binary tree after removing all leaf nodes with the specified target value, propagating the deletion upwards as needed.

Constraints:

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

Delete Leaves With a Given Value

Medium

Google

1 view

Topics:

TreesRecursion

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

For example:

Consider the following binary tree:

If target = 2, the algorithm should proceed as follows:

Initially, the leaf nodes with value 2 are removed:

    1
   / \
  _   3
 / \ / \
_  4 _  _

After removing the initial leaves, the nodes with value 2 which became leaf nodes are removed:

Consider the following binary tree:

    1
   / \
  3   3
 / \ / \
3  2 _  _

If target = 3, the algorithm should return:

Write a function that takes the root of a binary tree and a target value as input and returns the modified binary tree after removing all leaf nodes with the specified target value, propagating the deletion upwards as needed.

Constraints:

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

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the nodes in the tree and for the target value?
Can the tree be empty or contain only the root node? What should I return in those cases?
If multiple leaves have the target value and deleting them triggers further leaf deletions with the same value, should I recursively delete all such leaves until no more can be deleted?
Is the input a binary tree, a binary search tree, or a more general tree structure?
Should the function modify the original tree in place, or should it return a new tree?

Brute Force Solution

Approach

The brute force method attacks this problem by repeatedly checking and modifying the tree until no more changes can be made. We look for leaves with the target value and remove them. This process is repeated until there are no more leaves with that value left in the tree.

Here's how the algorithm would work step-by-step:

Inspect every leaf in the tree.
If any leaf's value matches the target value, remove that leaf from the tree.
After removing all the matching leaves in the initial pass, repeat the process.
Continue inspecting and removing leaves with the target value in successive rounds until no more leaves with the target value can be found anywhere in the tree.
The final remaining tree is the result.

Code Implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def delete_leaves_brute_force(root, target):
    if not root:
        return None

    while True:
        root, deleted_nodes = delete_leaves_once(root, target)

        # If we didn't delete any nodes, we're done
        if not deleted_nodes:
            break

    return root

def delete_leaves_once(root, target):
    deleted_nodes = False

    if not root:
        return None, deleted_nodes

    root.left, left_deleted = delete_leaves_once(root.left, target)
    root.right, right_deleted = delete_leaves_once(root.right, target)

    # Identify leaf nodes with the target value
    if root.left is None and root.right is None and root.val == target:
        return None, True

    if left_deleted or right_deleted:
        deleted_nodes = True

    return root, deleted_nodes

Big(O) Analysis

Time Complexity

O(n²) – The brute force approach involves repeated passes through the tree. In the worst case, each pass examines all n nodes of the tree to identify and remove target leaves. Since we may need to repeat this process multiple times until no more target leaves exist, and in the worst-case scenario we remove one leaf per pass until all or most leaves are removed that match the target (which could be proportional to n in the worst-case skewed tree). Therefore, the entire operation could iterate n times through the tree, each time taking O(n) operations. The total complexity becomes proportional to n * n, which simplifies to O(n²).

Space Complexity

O(N) – The brute force method, as described, implicitly utilizes the call stack due to the repeated inspection and potential modification of the tree. In the worst-case scenario, the height of the tree could be N (where N is the number of nodes), leading to N recursive calls being placed on the stack. Therefore, the auxiliary space required due to the recursion stack can be O(N). Note that no explicit auxiliary data structures (e.g., arrays, hashmaps) are mentioned in the description.

Optimal Solution

Approach

The trick is to work from the bottom up. If we remove leaf nodes first, it simplifies the tree structure, making the overall task easier. We repeatedly check for and remove leaf nodes with the target value until no more can be removed.

Here's how the algorithm would work step-by-step:

Start at the bottom of the tree - the leaf nodes.
Check each leaf node to see if its value matches the value we want to delete.
If a leaf node's value matches, remove it from the tree.
After removing a leaf node, check its parent. If the parent is now a leaf node (meaning it has no children) and its value matches the value we want to delete, remove the parent as well.
Continue this process, moving upwards through the tree, repeatedly removing leaf nodes with the specified value.
Keep repeating this process until no more leaf nodes with the target value can be removed. This means that all the nodes that can be deleted have been deleted.

Code Implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def delete_leaves(root, target):
    def remove_leaves(node, target_value):
        if not node:
            return None

        node.left = remove_leaves(node.left, target_value)
        node.right = remove_leaves(node.right, target_value)

        # Check if the current node is a leaf and has the target value.
        if not node.left and not node.right and node.val == target_value:
            return None

        return node

    # Keep removing leaves until no more can be removed.
    while True:
        original_root = root
        root = remove_leaves(root, target)
        # Check if the tree structure changed after removing leaves.
        if root == original_root:
            break

    return root

Big(O) Analysis

Time Complexity

O(n²) – The algorithm repeatedly traverses the tree, removing leaf nodes with the target value. In the worst-case scenario, each node might be visited multiple times. Imagine a tree where deleting leaves exposes new leaves with the target value in subsequent iterations. In the absolute worst-case situation, a single iteration could traverse close to all 'n' nodes. Because we repeat this until no more nodes can be removed, we could theoretically have to do up to 'n' iterations. Therefore the time complexity can be expressed as O(n * n) which is O(n²).

Space Complexity

O(H) – The dominant space complexity factor arises from the recursive calls. In the worst-case scenario, the recursion depth could be proportional to the height (H) of the binary tree, where each recursive call adds a new frame to the call stack. Thus, the auxiliary space required is directly related to the maximum height of the tree, representing the space used for storing the function call stack during recursion. Therefore, the space complexity can be expressed as O(H), where H is the height of the binary tree. Note that in the worst case (skewed tree), H can be N, and in the best case (balanced tree), H can be log N.

Edge Cases

Case	How to Handle
Null root node	Return null immediately as there's nothing to process.
Tree with only a root node, and its value equals the target	Return null as the entire tree is now deleted.
All leaf nodes have the target value	Repeated deletion will eventually eliminate the entire tree if interior nodes become leaves with the target value.
Tree with many nodes having the target value concentrated in a single subtree	The recursive calls handle subtree deletions effectively, ensuring correct pruning.
Deeply unbalanced tree to test recursion depth	Ensure the programming language's stack is large enough to avoid stack overflow errors, or convert to iterative approach if necessary.
Tree with no leaf nodes having the target value	The function should complete normally, leaving the tree unmodified.
The target value is the same as some, but not all, interior node values	Only leaf nodes matching the target value should be deleted, ensuring interior nodes are preserved unless they become leaves matching the target.
Memory constraints with a very large tree	Iterative solutions might be more memory efficient than recursive ones for extremely large trees.