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

Insufficient Nodes in Root to Leaf Paths

Difficulty: Medium

Problem Description

Given the root of a binary tree and an integer limit, delete all insufficient nodes in the tree simultaneously, and return the root of the resulting binary tree. A node is insufficient if every root to leaf path intersecting this node has a sum strictly less than the limit. A leaf is a node with no children.

Key Insights

  • A depth-first search (DFS) approach helps traverse the tree while calculating the path sums.
  • Nodes that do not contribute to any valid root-to-leaf path (sums >= limit) must be removed.
  • The recursion can return a null pointer for any insufficient nodes, effectively pruning the tree.

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 in DFS.

Solution

The solution employs a depth-first search (DFS) to traverse the binary tree while calculating the sum of values from the root to each node. If a node does not meet the sufficient condition (i.e., the sum of the path to its leaf nodes is less than the limit), it is removed from the tree. The algorithm continues this process recursively for both the left and right children of each node.

Code Solutions

def sufficientSubset(root, limit):
    def dfs(node, current_sum):
        if not node:
            return None
        
        current_sum += node.val
        
        # If it's a leaf node, check if it meets the limit
        if not node.left and not node.right:
            return node if current_sum >= limit else None
        
        # Recur for left and right children
        node.left = dfs(node.left, current_sum)
        node.right = dfs(node.right, current_sum)
        
        # If both children are insufficient, remove this node
        if not node.left and not node.right:
            return None
        
        return node
    
    return dfs(root, 0)
← Back to All Questions