# Solving Leetcode Interviews in Seconds with AI: Binary Tree Pruning


	# Introduction
	In this blog post, we will explore how to solve the LeetCode problem "814" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like [Chatmagic](https://www.chatmagic.app), we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

	# Problem Statement
	> 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:   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:   Input: root = [1,0,1,0,0,0,1] Output: [1,null,1,null,1]  Example 3:   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.  

	# Explanation
	*   **Post-order Traversal:** Perform a post-order traversal of the binary tree. This ensures that we process the children of a node before processing the node itself.
*   **Pruning Subtrees:** At each node, recursively check if its left and right subtrees contain a '1'. If a subtree does not contain a '1', prune it by setting the corresponding child pointer (left or right) to `None`.
*   **Node Evaluation:** A node itself "contains a 1" if its value is 1 or if either of its (potentially pruned) subtrees contain a 1. Return True if the node or any subtree contains 1, False otherwise.

*   **Time Complexity:** O(N), where N is the number of nodes in the tree. We visit each node once.
*   **Space Complexity:** O(H), where H is the height of the tree, due to the recursion stack. In the worst case (skewed tree), H = N, and in the best case (balanced tree), H = log N.

	
	# Code
	```python
	class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def pruneTree(root: TreeNode) -> TreeNode:
    """
    Prunes the binary tree such that every subtree not containing a 1 is removed.
    """

    def contains_one(node: TreeNode) -> bool:
        """
        Recursively checks if the subtree rooted at the given node contains a 1.
        """
        if not node:
            return False

        left_contains_one = contains_one(node.left)
        right_contains_one = contains_one(node.right)

        if not left_contains_one:
            node.left = None
        if not right_contains_one:
            node.right = None

        return node.val == 1 or left_contains_one or right_contains_one

    if not contains_one(root):
        return None
    return root
	```