Binary Tree Pruning

Problem

Return the same tree where every subtree not containing a 1 has been removed.

Key insight: Post-order. After pruning children, if a leaf is 0, return null.

Solutions

// C
TreeNode* pruneTree(TreeNode* root) {
    if (!root) return NULL;
    root->left = pruneTree(root->left);
    root->right = pruneTree(root->right);
    if (!root->left && !root->right && root->val == 0) return NULL;
    return root;
}

// C++
TreeNode* pruneTree(TreeNode* root) {
    if (!root) return nullptr;
    root->left = pruneTree(root->left);
    root->right = pruneTree(root->right);
    if (!root->left && !root->right && root->val == 0) return nullptr;
    return root;
}

// Java
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 && root.val == 0) return null;
    return root;
}

// JavaScript
function pruneTree(root) {
    if (!root) return null;
    root.left = pruneTree(root.left);
    root.right = pruneTree(root.right);
    if (!root.left && !root.right && root.val === 0) return null;
    return root;
}

# Python
def pruneTree(root):
    if not root:
        return None
    root.left = pruneTree(root.left)
    root.right = pruneTree(root.right)
    if not root.left and not root.right and root.val == 0:
        return None
    return root

Complexity

Time: O(n)
Space: O(h)