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

Insufficient Nodes in Root to Leaf Paths

Number: 1157

Difficulty: Medium

Paid? No

Companies: Amazon

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 considered insufficient if every root-to-leaf path that goes through that node has a sum of node values strictly less than limit.

Key Insights

  • Use a Depth-First Search (DFS) strategy, specifically a postorder traversal, so that decisions to prune nodes are made after processing their children.
  • At each leaf, directly compare the sum of the current path with the limit.
  • For internal nodes, recursively check their children; if both children are pruned (or become null), then assess the current node as a new leaf.
  • Maintain a running cumulative sum as you traverse from the root to each node.
  • The deletion (pruning) decision is ultimately determined by whether the cumulative sum(s) meet the given limit.

Space and Time Complexity

Time Complexity: O(n) - We visit each node exactly once. Space Complexity: O(h) - The space used is proportional to the height of the tree due to the recursion stack.

Solution

We solve the problem using a recursive postorder DFS approach. The algorithm works as follows:

  1. Start at the root and traverse down to the leaves, tracking the cumulative sum along the path.
  2. When reaching a leaf, check if the cumulative sum (including the leaf) is less than the limit; if so, prune the leaf by returning null.
  3. For non-leaf nodes, recursively perform the check on both children. After the recursive calls, if both children are pruned (null), then the current node is effectively a leaf and must be checked against the limit.
  4. Return the current node if it satisfies the conditions, otherwise return null.
  5. Finally, if the root is pruned, return null.

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 sufficientSubset(self, root: TreeNode, limit: int) -> TreeNode:
        # Recursive DFS function with postorder traversal
        def dfs(node, currentSum):
            if not node:
                return None
            
            # Update cumulative sum at the current node
            currentSum += node.val
            
            # If the node is a leaf, check if it meets the limit
            if not node.left and not node.right:
                return None if currentSum < limit else node
            
            # Recursively process left and right subtrees
            node.left = dfs(node.left, currentSum)
            node.right = dfs(node.right, currentSum)
            
            # If both subtrees are pruned then prune this node too
            if not node.left and not node.right:
                return None
            return node
        
        return dfs(root, 0)
← Back to All Questions