LeetCode 814 – Binary Tree Pruning: Problem Explanation and Solutions in Java, C++, and Python

One netizen recounts a JD interview where they passed multiple technical rounds but were rejected at the “personality” assessment, sparking comments about the absurdity of such a stage.

Following this anecdote, the article presents today’s algorithm question: LeetCode problem 814 – Binary Tree Pruning.

Problem description: Given the root of a binary tree where each node’s value is 0 or 1, return the tree after removing every subtree that does not contain a 1. A subtree consists of a node and all its descendants.

Examples:

Example 1: input root = [1,null,0,0,1] → output [1,null,0,null,1]. Only the red nodes satisfy the condition.

Example 2: input root = [1,0,1,0,0,0,1] → output [1,null,1,null,1].

Constraints: the number of nodes is in [1,200] and each node value is 0 or 1.

Problem analysis: Any subtree whose all nodes are 0 should be removed; if a subtree contains at least one 1 it must be kept. A post‑order traversal (bottom‑up) works because leaf nodes can be examined first, and after deleting children a parent may become a leaf.

Below are concise implementations using post‑order traversal in three languages.

Java:

// From bottom up, using post‑order traversal
public TreeNode pruneTree(TreeNode root) {
    if (root == null) return null;
    root.left = pruneTree(root.left);  // prune left subtree
    root.right = pruneTree(root.right); // prune right subtree
    // If leaf node value is 0, delete it
    if (root.left == null && root.right == null && root.val == 0)
        return null;
    return root;
}

C++:

public:
    TreeNode* pruneTree(TreeNode* root) {
        if (!root) return nullptr;
        root->left = pruneTree(root->left);   // prune left subtree
        root->right = pruneTree(root->right); // prune right subtree
        // Delete leaf node with value 0
        if (!root->left && !root->right && !root->val)
            return nullptr;
        return root;
    }

Python:

# From bottom up, using post‑order traversal
def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
    if not root:
        return root
    root.left = self.pruneTree(root.left)   # prune left subtree
    root.right = self.pruneTree(root.right) # prune right subtree
    # Delete leaf node with value 0
    if not root.left and not root.right and root.val == 0:
        return None
    return root