Taro Logo

Delete Leaves With a Given Value

Medium
Google logo
Google
0 views
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:

    1
   / \
  2   3
 / \ / \
2  4 2  2

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

  1. Initially, the leaf nodes with value 2 are removed:
    1
   / \
  _   3
 / \ / \
_  4 _  _
  1. After removing the initial leaves, the nodes with value 2 which became leaf nodes are removed:
    1
     \
      3
     / 
    4  

Consider the following binary tree:

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

If target = 3, the algorithm should return:

    1
   / \
  3   _
     / 
    2  

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


Naive Solution

A brute-force approach would involve traversing the tree and identifying leaf nodes with the target value. If such a node is found, it's removed. After the removal, the tree is re-evaluated to see if the removal created new leaf nodes with the target value, repeating until no more such nodes exist.

Code (Python)

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

def remove_leaf_nodes(root, target):
    dummy = TreeNode(0)
    dummy.left = root
    
    def remove(node, parent, is_left):
        if not node:
            return None
        
        node.left = remove(node.left, node, True)
        node.right = remove(node.right, node, False)
        
        if not node.left and not node.right and node.val == target:
            if parent:
                if is_left:
                    parent.left = None
                else:
                    parent.right = None
            return None
            
        return node

    dummy.left = remove(root, dummy, True)
    return dummy.left

Time Complexity

O(N*K), where N is the number of nodes in the tree, and K is the number of times we have to repeat the process of removing leaves. In the worst case, K could be O(N).

Space Complexity

O(H), where H is the height of the tree, due to the recursion stack.

Optimal Solution

A more efficient solution uses a post-order traversal. We process the children of a node before processing the node itself. This allows us to identify and remove leaf nodes during the traversal, naturally propagating changes up the tree.

Code (Python)

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

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

    root.left = remove_leaf_nodes(root.left, target)
    root.right = remove_leaf_nodes(root.right, target)

    if not root.left and not root.right and root.val == target:
        return None

    return root

Time Complexity

O(N), where N is the number of nodes in the tree. Each node is visited exactly once.

Space Complexity

O(H), where H is the height of the tree, due to the recursion stack. In the worst-case (skewed tree), H can be O(N), and in the best case (balanced tree), H can be O(log N).

Edge Cases

  • Empty Tree: The function should handle an empty tree gracefully (returning None).
  • Target Not Found: If the target value isn't present, the tree should remain unchanged.
  • Root is Target: The root itself might need to be deleted, so consider the case where the root becomes None.
  • Tree of All Targets: Consider the case where the entire tree contains the target value, and all nodes are eventually removed.