814. Binary Tree Pruning LeetCode Solution

In this guide, you will get 814. Binary Tree Pruning LeetCode Solution with the best time and space complexity. The solution to Binary Tree Pruning problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Binary Tree Pruning solution in C++
Binary Tree Pruning solution in Java
Binary Tree Pruning solution in Python
Additional Resources

814. Binary Tree Pruning LeetCode Solution image

Problem Statement of Binary Tree Pruning

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.

Complexity Analysis

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

814. Binary Tree Pruning LeetCode Solution in C++

class Solution {
 public:
  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 && root->val == 0)
      return nullptr;
    return root;
  }
};
/* code provided by PROGIEZ */

814. Binary Tree Pruning LeetCode Solution in Java

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;
  }
}
// code provided by PROGIEZ

814. Binary Tree Pruning LeetCode Solution in Python

class Solution:
  def pruneTree(self, root: TreeNode | None) -> TreeNode | None:
    if not root:
      return None
    root.left = self.pruneTree(root.left)
    root.right = self.pruneTree(root.right)
    if not root.left and not root.right and not root.val:
      return None
    return root
 # code by PROGIEZ