[Solved] Given the root of a binary tree, return the same tree where every subtree (of the given tree) not containing a 1 has been removed. A subtree of a node node is node plus every node that is a descendant of node.

Question

Given the root of a binary tree, return the same tree where every subtree (of the given tree) not containing a 1 has been removed.

A subtree of a node node is node plus every node that is a descendant of node.

Example 1:

Machine Learning Projects
Input: root = [1,null,0,0,1]
Output: [1,null,0,null,1]
Explanation: 
Only the red nodes satisfy the property "every subtree not containing a 1".
The diagram on the right represents the answer.

Example 2:

Machine Learning Projects
Input: root = [1,0,1,0,0,0,1]
Output: [1,null,1,null,1]

Example 3:

Machine Learning Projects
Input: root = [1,1,0,1,1,0,1,0]
Output: [1,1,0,1,1,null,1]

Constraints:

  • The number of nodes in the tree is in the range [1, 200].
  • Node.val is either 0 or 1.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
def prune(root,parent):
    if root==None:return
    
    prune(root.left,root)
    prune(root.right,root)
    if root.left==None and root.right==None and root.val==0:
        if parent.left == root:
            parent.left = None
        else:    
            parent.right = None
    

class Solution:
    def pruneTree(self, root: TreeNode) -> TreeNode:
        prune(root,None)
        return root
Abhishek Sharma
Abhishek Sharma

Started my Data Science journey in my 2nd year of college and since then continuously into it because of the magical powers of ML and continuously doing projects in almost every domain of AI like ML, DL, CV, NLP.

Articles: 514

Leave a Reply

Your email address will not be published. Required fields are marked *