LeetCode 814: Binary Tree Pruning

Problem (LeetCode 814): Given the root of a binary tree where each node's value is either 0 or 1, return the tree after removing all subtrees that do not contain a 1.

Input example: root = [1,null,0,0,1]

Output example: [1,null,0,null,1]

The solution uses a post‑order recursion: recursively prune the left and right subtrees, then decide whether to keep the current node based on its children and its own value.

Recursive algorithm (in pseudocode):

function pruneTree(node):
    if node is null:
        return null
    node.left = pruneTree(node.left)
    node.right = pruneTree(node.right)
    if node.left != null or node.right != null:
        return node
    return node if node.val == 1 else null

Time complexity: O(n) where n is the number of nodes. Space complexity: O(h) for recursion stack, h = tree height.

Reference implementations:

class Solution {
    public TreeNode pruneTree(TreeNode root) {
        if (root == null) return null;
        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);
        if (root.left != null || root.right != null) return root;
        return root.val == 0 ? null : root;
    }
}

class Solution {
    TreeNode* pruneTree(TreeNode* root) {
        if (root == nullptr) return nullptr;
        root->left = pruneTree(root->left);
        root->right = pruneTree(root->right);
        if (root->left != nullptr || root->right != nullptr) return root;
        return root->val == 0 ? nullptr : root;
    }
};

class Solution:
    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        root.left = self.pruneTree(root.left)
        root.right = self.pruneTree(root.right)
        if root.left or root.right:
            return root
        return None if root.val == 0 else root

function pruneTree(root: TreeNode | null): TreeNode | null {
    if (root == null) return null;
    root.left = pruneTree(root.left);
    root.right = pruneTree(root.right);
    if (root.left != null || root.right != null) return root;
    return root.val == 0 ? null : root;
}