Binary Tree Pruning - Leetcode Solution

Problem:

Given the root of a binary tree rooted at node 0, return the same tree where every subtree (of the given tree rooted at a node) 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: Input: [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.

Solution:

This problem can be solved using recursion. We can traverse the binary tree in a post-order fashion and remove the nodes which do not contain a 1.

In order to check if a subtree contains a 1, we need to traverse the left and right subtrees of the current node and check if they contain a 1.

If the left subtree does not contain a 1, we can set the left child of the current node to null. Similarly, if the right subtree does not contain a 1, we can set the right child of the current node to null.

We can then return true if the current node contains a 1 or if its left or right subtree contains a 1.

Here is the detailed algorithm:

1. If the root node is null, return false.
2. Recursively check if the left subtree contains a 1.
3. Recursively check if the right subtree contains a 1.
4. If the left subtree does not contain a 1, set the left child of the current node to null.
5. If the right subtree does not contain a 1, set the right child of the current node to null.
6. If the current node contains a 1 or if its left or right subtree contains a 1, return true.
7. Otherwise, return false.

Here is the Python implementation of the above algorithm:

class Solution:
    def pruneTree(self, root: TreeNode) -> TreeNode:
        if root is None:
            return None
        
        left_has_one = self.pruneTree(root.left)
        right_has_one = self.pruneTree(root.right)
        
        if not left_has_one:
            root.left = None
        
        if not right_has_one:
            root.right = None
            
        return root.val == 1 or left_has_one or right_has_one

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 (the maximum number of recursive calls on the call stack at any given time). In the worst case, the binary tree is skewed and the height is O(n), so the space complexity is O(n).

1