LeetCode 814: Binary Tree Pruning Solution

Master LeetCode problem 814 (Binary Tree Pruning), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

814. Binary Tree Pruning

Medium

Tree Depth-First Search Binary Tree

Problem Explanation

Explanation

To solve this problem, we can perform a post-order traversal of the tree. At each node, we recursively check the left and right subtrees. If both subtrees do not contain any 1, and the current node also does not have a value of 1, we can prune the subtree rooted at the current node by returning null. Otherwise, we return the current node.

Algorithm

Recursively prune the left subtree.
Recursively prune the right subtree.
Check if the current node is a leaf and has a value of 0, prune it by returning null.
Return the current node.

Time Complexity

The time complexity of this approach is O(N), where N is the number of nodes in the tree. We visit each node once during the post-order traversal.

Space Complexity

The space complexity is also O(N) due to the recursive calls on the stack.

Solution Code

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

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 814 (Binary Tree Pruning)?

This page provides optimized solutions for LeetCode problem 814 (Binary Tree Pruning) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 814 (Binary Tree Pruning)?

The time complexity for LeetCode 814 (Binary Tree Pruning) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 814 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 814 in Java, C++, or Python.

Back to LeetCode Solutions