Delete Leaves With a Given Value
Medium
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:
- 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:
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.
