Solution Explanation: Binary Tree Pruning

This problem asks us to prune a binary tree, removing all subtrees that do not contain the value 1. A subtree is defined as a node and all its descendants. The solution uses a recursive depth-first search (DFS) approach.

Approach:

The core idea is to recursively process the tree from the leaves upwards. For each node:

1. Base Case: If the node is null, we return null.

2. Recursive Step: We recursively call pruneTree on the left and right subtrees. This ensures that the pruning is done from the bottom of the tree upwards. The results of these recursive calls are then assigned back to the current node's left and right children.

3. Pruning Condition: If the current node's value is 0 AND both its left and right children are null (meaning the subtree rooted at this node contains only 0s), we return null, effectively removing this subtree.

4. Otherwise: If the node's value is 1 or it has at least one non-null child after the recursive pruning, we return the current node, keeping it in the tree.

Time and Space Complexity Analysis:

• Time Complexity: O(N), where N is the number of nodes in the tree. This is because we visit each node exactly once during the recursive traversal.

• Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack. In the worst case (a skewed tree), H could be N, resulting in O(N) space complexity. However, in a balanced tree, H would be log₂(N), leading to O(log₂(N)) space complexity.

Code Implementation (Python):

# 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
 
class Solution:
    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root is None:
            return None  # Base case: empty subtree
 
        root.left = self.pruneTree(root.left)  # Recursively prune left subtree
        root.right = self.pruneTree(root.right) # Recursively prune right subtree
 
        if root.val == 0 and root.left is None and root.right is None:
            return None  # Pruning condition: node is 0 and has no children
 
        return root  # Keep the node

The implementations in other languages (Java, C++, Go, TypeScript, Rust, JavaScript) follow the same logic, adapting the syntax and data structures to their respective languages. The core recursive approach and pruning condition remain consistent across all implementations.