Delete Leaves With a Given Value

Jyothi
2 min readApr 4, 2022

--

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)

Problem is actually easy level and is easy to understand.
This is similar to House robber-III problem as to start trimming from leaf nodes and go up.
So post-order DFS approach is better for this problem.
Below is the C solution:

void rmLfNodes(struct TreeNode *nd, struct TreeNode *parent, bool left, int target){
/* if no node or value not matching */
if (!nd) return;
rmLfNodes(nd->left, nd, 1, target);
rmLfNodes(nd->right, nd, 0, target);
if (!nd->left && !nd->right && nd->val == target){
if (left)
parent->left = NULL;
else
parent->right = NULL;
free(nd);
}
return;
}
struct TreeNode* removeLeafNodes(struct TreeNode* root, int target){
if (!root) return NULL;
rmLfNodes(root->left, root, 1, target);
rmLfNodes(root->right, root, 0, target);
if (!root->left && !root->right && root->val == target)
return NULL;
return root;
}

I think we can still optimize, please provide your feedback.

Below is Python sol, we can still optimize by passing or checking parent as NULL

class Solution(object):
def helper(self, nd, parent, target):
if (nd is None):
return
self.helper(nd.left, nd, target)
self.helper(nd.right, nd, target)
if ((nd.left is None) and (nd.right is None) and
(nd.val == target)):
if (parent.left == nd):
parent.left = None
else:
parent.right = None
return

def removeLeafNodes(self, root, target):
"""
:type root: TreeNode
:type target: int
:rtype: TreeNode
"""
if (root is None):
return None
self.helper(root.left, root, target)
self.helper(root.right, root, target)
if ((root.left == None) and (root.right == None) and
(root.val == target)):
return None
return root;

--

--

No responses yet