We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Binary Tree Pruning

Number: 832

Difficulty: Medium

Paid? No

Companies: Meta, Hulu

Problem Description

Given the root of a binary tree where each node is either 0 or 1, remove every subtree that does not contain a 1. A subtree is defined as a node plus all its descendants. The pruned tree should only contain nodes which are either 1 or have at least one descendant with a 1.

Key Insights

  • Use a postorder DFS traversal so that you process the children before the parent.
  • At each node, recursively check and prune the left and right subtrees.
  • If a node’s left and right subtrees are pruned away (i.e. become null) and the node’s value is 0, prune the node itself.
  • The process simultaneously checks for the condition and rebuilds the tree by linking only necessary nodes.

Space and Time Complexity

Time Complexity: O(n) where n is the number of nodes in the tree, since every node is visited once. Space Complexity: O(n) in the worst case due to recursion stack space in the case of a skewed tree.

Solution

The solution employs a recursive postorder DFS that processes the left and right subtrees first, then checks the current node. For each node, if both left and right subtrees do not contain 1 (i.e., have been pruned to null) and the current node’s value is 0, the current node is pruned by returning null. This approach ensures that the tree is pruned from the bottom up, preserving nodes that are required to satisfy the condition that at least one node in the subtree has a value of 1.

Code Solutions

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def pruneTree(self, root: TreeNode) -> TreeNode:
        # Base case: If the current node is None, return None
        if not root:
            return None
        
        # Recursively prune the left subtree
        root.left = self.pruneTree(root.left)
        # Recursively prune the right subtree
        root.right = self.pruneTree(root.right)
        
        # If the current node's value is 0 and both children are pruned away (None), prune current node
        if root.val == 0 and not root.left and not root.right:
            return None
        
        # Otherwise, keep the current node
        return root
← Back to All Questions