Problem statement

1080. Insufficient Nodes in Root to Leaf Paths

Solution

In this problem we need to use postorder dfs: dfs(node, sm) means that we reached node and sm is sum of values from root to node, not including node.

  1. If we reached None node, return False, we do not need to delete it.
  2. If we reached leaf, check if sm + node.val >= limit, it will say if we need to delete it.
  3. Traverse left and right subtrees.
  4. If answer for the left subtree is False, remove this subtee, the same for the right subtree.
  5. Finally, If any of two subtees are not deleted, keep node, in the opposite case delete it as well.

Complexity

It is O(n) for time and O(h) for space.

Code

class Solution:
    def sufficientSubset(self, root, limit):
        def dfs(node, sm):
            if not node: return False
            if not node.left and not node.right:
                return sm + node.val >= limit
            left = dfs(node.left, sm + node.val)
            right = dfs(node.right, sm + node.val)
            if not left:
                node.left = None
            if not right:
                node.right = None
            
            return left or right
        
        result = dfs(root, 0)
        return root if result else None