Delete Leaves With A Given Value - Leetcode Solution

Problem Statement:

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 it's parent node becomes a leaf node and has the value target, it should also be deleted (you need to continue doing that until you can't).

Example 1:

Input: root = [1,2,3,2,null,2,4], target = 2 Output: [1,null,3,null,4] Explanation: Leaf nodes in green with value (target = 2) are removed (Picture in the above link). Example 2:

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

Input: root = [1,2,null,2,null,2], target = 2 Output: [1] Explanation: Leaf nodes in green with value (target = 2) are removed.

Approach:

• We'll recurse on the left subtree and right subtree, and then check that if the root has target value and is a leaf node, then return null.
• If its left and right subtrees are null, and the root of the current subtree has the target value, return null.
• If the root is null, return null.
• Return the current root.

Code:

/**

• Definition for a binary tree node.
• struct TreeNode {

• int val;
  

• TreeNode *left;
  

• TreeNode *right;
  

• TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  

• }; / class Solution { public: TreeNode removeLeafNodes(TreeNode* root, int target) { if(!root) return nullptr; root->left = removeLeafNodes(root->left,target); root->right = removeLeafNodes(root->right,target); if(!root->left && !root->right && root->val == target) return nullptr; return root; } };

Time Complexity: O(n) where n is the number of nodes in the binary tree.

Space Complexity: O(H), where H is the height of the binary tree.

1