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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Binary Tree Pruning

Difficulty: Medium

Problem Description

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.

Key Insights

  • We need to traverse the binary tree to check each subtree for the presence of the value 1.
  • If a subtree does not contain 1, it should be pruned (removed).
  • A depth-first search (DFS) approach is suitable for this problem as it allows us to explore each subtree fully before making decisions about its removal.
  • The pruning operation must ensure that the tree structure remains valid after removing nodes.

Space and Time Complexity

Time Complexity: O(N), where N is the number of nodes in the tree, as we need to visit each node once. Space Complexity: O(H), where H is the height of the tree, due to the recursion stack used in depth-first search.

Solution

To solve the problem, we will use a depth-first search (DFS) approach. We will traverse the tree starting from the root node. For each node, we will recursively check its left and right children. If both children do not contain 1, we will prune them by setting them to null. Finally, we will return the modified tree with all subtrees not containing 1 removed.

Code Solutions

def pruneTree(root):
    # Helper function to perform DFS and prune the tree
    def dfs(node):
        # If the node is None, return None
        if not node:
            return None
        
        # Recursively prune the left and right subtrees
        node.left = dfs(node.left)
        node.right = dfs(node.right)
        
        # If the current node is 0 and both subtrees are None, prune it
        if node.val == 0 and not node.left and not node.right:
            return None
        
        return node
    
    return dfs(root)
← Back to All Questions