Given the root of a binary tree, consider all root to leaf paths: paths from the root to any leaf.  (A leaf is a node with no children.)
A node is insufficient if every such root to leaf path intersecting this node has sum strictly less than limit.
Delete all insufficient nodes simultaneously, and return the root of the resulting binary tree.
 
Example 1:

Input: root = [1,2,3,4,-99,-99,7,8,9,-99,-99,12,13,-99,14], limit = 1

Output: [1,2,3,4,null,null,7,8,9,null,14]


Example 2:

Input: root = [5,4,8,11,null,17,4,7,1,null,null,5,3], limit = 22

Output: [5,4,8,11,null,17,4,7,null,null,null,5]
 
Example 3:

Input: root = [1,2,-3,-5,null,4,null], limit = -1

Output: [1,null,-3,4]

 
Note:

The given tree will have between 1 and 5000 nodes.
-10^5 <= node.val <= 10^5
-10^9 <= limit <= 10^9

Difficulty: interview

Starter code:

# 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:
        

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, limit):
        if root.left == root.right:
            return None if root.val < limit else root
        if root.left:
            root.left = self.sufficientSubset(root.left, limit - root.val)
        if root.right:
            root.right = self.sufficientSubset(root.right, limit - root.val)
        return root if root.left or root.right else None


# 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:
        if root.left == root.right:
            return None if root.val < limit else root
        if root.left:
            root.left = self.sufficientSubset(root.left, limit - root.val)
        if root.right:
            root.right = self.sufficientSubset(root.right, limit - root.val)
        return root if root.left or root.right else None

# 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 sumofnodes(self,root,cursum):
        if root is None :
            return 0
        cursum += root.val 
        self.sumdict[root] = cursum
        self.sumofnodes(root.left,cursum)
        self.sumofnodes(root.right,cursum)
        
    def maxpathsum(self,root):
        #leaf
        if root.left == None and root.right == None:
            self.maxdict[root] = self.sumdict[root]
        # max among two paths
        elif root.left and root.right:
            self.maxdict[root] = max(self.maxpathsum(root.left),self.maxpathsum(root.right))
        # single path
        elif root.right:
            self.maxdict[root] = self.maxpathsum(root.right)
        # single path
        else :
            self.maxdict[root] = self.maxpathsum(root.left)
        # this takes care of root is none returning 0 messing with out paths
        return self.maxdict[root]
           
     
    def deletenodes(self,root,limit):
        if root is None:
            return
        
        if root.left and self.maxdict[root.left] < limit:
            root.left = None
        if root.right and self.maxdict[root.right] < limit:
            root.right = None
        self.deletenodes(root.left,limit)
        self.deletenodes(root.right,limit)
        
    def sufficientSubset(self, root: TreeNode, limit: int) -> TreeNode:
        self.sumdict = {}
        self.sumofnodes(root,0)
        self.maxdict = {}
        self.maxpathsum(root)
        # if maxpathsum along this node is less than limit, delete
        self.deletenodes(root,limit)
        if self.maxdict[root] < limit:
            return None
        else:
            return root
        
        
        
        
        
        
            


# 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, limit):
        
        def dfs(root, cur):
            if root is None:
                return None
            s = root.val + cur
            if root.left is None and root.right is None:
                if s < limit:
                    return None
                else:
                    return root
            l = dfs(root.left, s)
            r = dfs(root.right, s)
            if l is None and r is None:
                return None
            root.left, root.right = l, r
            return root
        
        return dfs(root, 0)
        


# 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:
        if root is None:
            return None
        
        print(root.val, limit)
        
        # If we have reached a root
        if root.left is None and root.right is None:
            if root.val < limit:
                return None
            else:
                return root
            
        left = self.sufficientSubset(root.left, limit - root.val)
        right = self.sufficientSubset(root.right, limit - root.val)
        
        if left is None and right is None:
            return None
        else:
            root.left = left
            root.right = right
            return root

# 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:
        sum_t_root = TreeNode(root.val)
        sum_t_node = sum_t_root
        t_node = root
        
        def calSumT(node, sum_t_node, s):
            if not node: return
            # print (node.val)
            if not node.left and not node.right:
                sum_t_node.val = True if s >= limit else False
            if node.left:
                sum_t_node.left = TreeNode(node.left.val+s)
                calSumT(node.left, sum_t_node.left, s+node.left.val)
            if node.right:
                sum_t_node.right = TreeNode(node.right.val+s)
                calSumT(node.right, sum_t_node.right, s+node.right.val)

        
        calSumT(t_node, sum_t_node, root.val)
        
        def strT(node):
            if not node: return []
            return [node.val]+strT(node.left)+strT(node.right)
        
        # print (strT(sum_t_root))
        
        def checkSumT(node):
            if not node.left and not node.right: return
            rtn = False
            if node.left:
                checkSumT(node.left)
                rtn |= node.left.val
            if node.right: 
                checkSumT(node.right)
                rtn |= node.right.val
            node.val = rtn
            
        sum_t_node = sum_t_root    
        checkSumT(sum_t_node)
        # print (strT(sum_t_root))
        
        def updateNode(node, s_node):
            if not node or not s_node.val: return None
            # print (node.val)
            if node.left:
                node.left = updateNode(node.left, s_node.left)
            if node.right:
                node.right = updateNode(node.right, s_node.right)
            return node
        
        return updateNode(root, sum_t_root)


# 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 check_limit(self, root, limit):
        if not root:
            return float('-inf')
        
        left_sum = self.check_limit(root.left, limit-root.val)
        right_sum = self.check_limit(root.right, limit-root.val) 
        
        if left_sum != float('-inf') and left_sum+root.val < limit:
            root.left = None
        if right_sum != float('-inf') and right_sum+root.val < limit:
            root.right = None
        
        max_ = max(left_sum, right_sum)
        if max_ == float('-inf'):
            return root.val
        return max_ + root.val

    def sufficientSubset(self, root: TreeNode, limit: int) -> TreeNode:
        if (self.check_limit(root, limit) or 0) < limit:
            return None
        else:
            return root

# 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:
        def check(node, pathsum):
            if not node:
                return pathsum >= limit
            pathsum += node.val
            had_children = node.left or node.right
            if not check(node.left, pathsum):
                node.left = None
            if not check(node.right, pathsum):
                node.right = None
            return node.left or node.right if had_children else pathsum >= limit
        
        return root if check(root, 0) else None

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

class Solution:
    def sufficientSubset(self, root: TreeNode, limit: int) -> TreeNode:
        def check(root, total, limit):
            #   返回：子树的路径的最大值
            if root == None:
                return None
            total += root.val

            #   当前是叶节点，判断状态并返回
            if root.left == root.right:
                if total < limit:
                    return None
                else:
                    return root
            
            flag1 = 0   #   0-不考虑、-1为失败、1为成功
            flag2 = 0
            if root.left:
                root.left = check(root.left,  total, limit)
                flag1 = 1 if root.left  else -1
            if root.right:
                root.right= check(root.right, total, limit)
                flag2 = 1 if root.right else -1

            if flag1 > 0 or flag2 > 0:
                return root
            else:
                return None
        
        rtv = check(root, 0, limit)
        return rtv




# 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:
        
        
        if not root:
            return root
        
        def dfs(node, value):
            if not node:
                return False
            
            value+=node.val
            lret = dfs(node.left, value)
            rret = dfs(node.right, value)
            if not node.left and not node.right:
                if value < limit:
                    return False
                return True
            
            if not lret:
                node.left = None
            if not rret:
                node.right = None
            
            if lret or rret:
                return True
            return False
        
        res = dfs(root, 0)
        if res:
            return root


# 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:
        def helper(root, currsum, limit):
            if not root:
                return True
            currsum += root.val
            if root.left is None and root.right is None:
                return currsum < limit
            
            deleteme = [True, True]
            
            if root.left:
                should_del = helper(root.left, currsum, limit)
                if should_del:
                    del root.left
                    root.left = None
                deleteme[0] = should_del
            
            if root.right:
                should_del = helper(root.right, currsum, limit)
                if should_del:
                    del root.right
                    root.right = None
                deleteme[1] = should_del
            
            return all(deleteme)
        
        deleteroot = helper(root, 0, limit)
        if deleteroot:
            del root
            return None
        return root

# 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:
        head=TreeNode()
        head.left=root
        
        def inner1(root, prev_sum):
            if root is None:
                return
            else:
                root.val=(root.val, prev_sum)
                inner1(root.left, root.val[0]+prev_sum)
                inner1(root.right, root.val[0]+prev_sum)
                return
        
        def inner2(root):
            if root is None:
                return []
            if root.left is None and root.right is None:
                return [sum(root.val)]
            left=inner2(root.left)
            if not left or max(left)<limit:
                root.left=None
            right=inner2(root.right)
            if not right or max(right)<limit:
                root.right=None
            res=left+right
            return res
        
        def inner3(root):
            if root is None:
                return
            else: 
                root.val=root.val[0]
                inner3(root.left)
                inner3(root.right)
                return
        
        inner1(head,0)
        _=inner2(head)
        inner3(head)
        return head.left

# 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:
        
        def generateSumT(node, s):
            if not node: return (None, False)
            if not node.left and not node.right:
                if s >= limit: 
                    # print (\"valid leaf\", node.val, s)
                    return (node, True) 
                else: return (None, False)
                
            isValid = False
            if node.left:
                node.left, L = generateSumT(node.left, s+node.left.val)
                isValid |= L
            if node.right:
                node.right, R = generateSumT(node.right, s+node.right.val )
                isValid |= R
                
            if isValid:
                return (node, True)
            else:
                return (None, False)
        
        rtn, _ = generateSumT(root, root.val)
        
#         def strT(node):
#             if not node: return []
#             return [node.val]+strT(node.left)+strT(node.right)
        
#         print (strT(rtn))
        
#         def updateNode(node, s_node):
#             if not node or not s_node.val: return None
#             # print (node.val)
#             if node.left:
#                 node.left = updateNode(node.left, s_node.left)
#             if node.right:
#                 node.right = updateNode(node.right, s_node.right)
#             return node
        
        return rtn


# 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
'''
Key concept:
    1. if left path sum < limit we remove left child and similarly remove right child
    2. The trick is when a node has only one child then what do we return? We just
    return the path sum computed for non null children
    
'''

class Solution:
    def sufficientSubset(self, root: TreeNode, limit: int) -> TreeNode:
        
        def remove(node, val):
            if not node: return val
            l = remove(node.left, node.val+val)
            r = remove(node.right, node.val+val)
            
            
            result = 0
            if node.left and node.right:
                result = max(l,r)
            elif node.left:
                result = l
            else: #node.right = None or both left right are None
                result = r
            
            if l<limit:
                node.left = None
            if r<limit:
                node.right = None
            
            return result
            
        val = remove(root,0)
        
        return None if val < limit else root


# 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:
        
        def remove(node, val):
            if not node: return val
            l = remove(node.left, node.val+val)
            r = remove(node.right, node.val+val)
            
            
            result = 0
            if node.left and node.right:
                result = max(l,r)
            elif node.left:
                result = l
            else: #node.right = None or both left right are None
                result = r
            
            if l<limit:
                node.left = None
            if r<limit:
                node.right = None
            
            return result
            
        val = remove(root,0)
        
        return None if val < limit else root


# 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:
        
        if not root:
            return root
        if not root.left and not root.right:
            return root if root.val >= limit else None
        
        root.left = self.sufficientSubset(root.left, limit-root.val)
        root.right = self.sufficientSubset(root.right, limit-root.val)
        
        return root if root.left or root.right else None

# 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:
        
        def dfs(node,value):
            if not node:
                return False
            value+=node.val
            l=dfs(node.left,value)
            r=dfs(node.right,value)
            if not node.left and not node.right:
                if value<limit:
                    return False
                return True
            if not l:
                node.left=None
            if not r:
                node.right=None
            if l or r:
                return True
            return False
        res=dfs(root,0)
        if res:
            return root
        return 

# 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:
        
        if root.left == root.right:
            if root.val < limit:
                return None
            else:
                return root
            
        if root.left:
            root.left = self.sufficientSubset(root.left, limit - root.val)

        if root.right:
            root.right = self.sufficientSubset(root.right, limit - root.val)
            
        return root if root.left or root.right else None


# 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

def collect_insufficient_nodes(node, cur_sum, nodes, limit):
    if node is None:
        return 0
    
    subpath_sums = []
    if node.left:
        subpath_sums.append(collect_insufficient_nodes(node.left, cur_sum + node.val, nodes, limit))
    if node.right:
        subpath_sums.append(collect_insufficient_nodes(node.right, cur_sum + node.val, nodes, limit))
                                
    max_subpath_sum = 0 if not len(subpath_sums) else max(subpath_sums)
    
    if cur_sum + max_subpath_sum + node.val < limit:
        nodes.append(node)
        
    return max_subpath_sum + node.val


def delete_nodes(node, nodes):
    if not node:
        return
    
    if node.left in nodes:
        node.left = None
    else:
        delete_nodes(node.left, nodes)
        
    if node.right in nodes:
        node.right = None
    else:
        delete_nodes(node.right, nodes)
        


class Solution:
    def sufficientSubset(self, root: TreeNode, limit: int) -> TreeNode:
        nodes = []
        collect_insufficient_nodes(root, 0, nodes, limit)
        nodes = set(nodes)
        if root in nodes:
            return None
        delete_nodes(root, nodes)
        return root
        


# 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:
        def dfs(node, path_sum):
            # parent has one child
            if not node:
                return False
            path_sum += node.val
            # if leaf
            if not node.left and not node.right:
                return path_sum >= limit
            left = dfs(node.left, path_sum)
            right = dfs(node.right, path_sum)
            # delete here itself
            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
        
        
        
        
        
        
            


# 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:
        \"\"\"
        return the root so that every node is a sufficient
        Approach:
        1. For any given node, if all of its children have a path sum < than limit, or None, delete the node
        2. Post-order traversal, at the leaf node, if the path sum < than limit, delete node, then work your way up
        \"\"\" 
        
        leaf = True
        # check left child alive
        if root.left is not None:
            root.left = self.sufficientSubset(root.left, limit - root.val)
            leaf = False
            
        # check right child alive
        if root.right is not None:
            root.right = self.sufficientSubset(root.right, limit - root.val)   
            leaf = False
            
        # if the node is not leaf and left and right are not alive -> set to null
\t\t# if the node is leaf but less than limit -> set to null
        if root.left is None and root.right is None and ( root.val < limit or not leaf):
            root = None

        return root
                
                
                
            
                

# 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:
        def dfs(node, value):
            if not node:
                return False
            value += node.val
            l_side = dfs(node.left,value)
            r_side = dfs(node.right,value)
            if not node.left and not node.right:
                if value < limit:
                    return False
                return True
            if not l_side:
                node.left = None
            if not r_side:
                node.right = None
            if l_side or r_side:
                return True
            return False
        if dfs(root, 0):
            return root
        return           


# 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:
        
        if (root==None):
            return None
        
        def dfs(root,val):
            
            if (root == None):
                return -10e9,'nodel'
            
            if (root):
                left_val,left_del_str = dfs(root.left,val+root.val)
                right_val,right_del_str = dfs(root.right,val+root.val)
                
                if (root.left and root.right):
                    cur_val = val + root.val + max(left_val,right_val)
                elif (root.left):
                    cur_val = val + root.val + left_val
                elif (root.right):
                    cur_val = val + root.val + right_val
                else:
                    cur_val = val + root.val
                
                #print (cur_val,root.val)
                
                if (left_del_str == 'del'):
                    root.left = None
                    
                if (right_del_str == 'del'):
                    root.right = None
                    
                if (cur_val<limit):
                    return cur_val-val,'del'
                else:
                    return cur_val-val,'nodel'
                
        _,root_del_str = dfs(root,0)
        
        if (root_del_str == 'del'):
            return None
        else:
            return root
            


# 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:  
        if root == None:
            return None
        
        canRootLeft = self.validSubtree(root.left, limit, root.val)
        canRootRight = self.validSubtree(root.right, limit, root.val)
        
        root.left = (root.left if canRootLeft else None)
        root.right = (root.right if canRootRight else None)
        
        if not canRootLeft and not canRootRight:
            return None
        else:
            return root
        
    def validSubtree(self, node: TreeNode, limit: int, currentVal: int) -> bool:
        # Handling base-case leafs
        if node == None:
            return (currentVal >= limit)
        
        canLeft = self.validSubtree(node.left, limit, node.val + currentVal)
        canRight = self.validSubtree(node.right, limit, node.val + currentVal)
        
        # Handling single-branch values
        if (node.left and not node.right):
            # Using our node left value
            canRight = canLeft
        elif (node.right and not node.left):
            canLeft = canRight
        
        node.left = (node.left if canLeft else None)
        node.right = (node.right if canRight else None)
        
        if not canLeft and not canRight:
            return False
        else:
            return canLeft or canRight

# 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 helper(self, root, total, limit):
        if not root:
            return False
        
        if root.left == None and root.right == None:
            return total+root.val >= limit
        
        left = self.helper(root.left, total+root.val, limit)
        right = self.helper(root.right, total+root.val, limit)
        
        if not left:
            root.left = None
        if not right:
            root.right = None
        
        return left or right
    
    def sufficientSubset(self, root: TreeNode, limit: int) -> TreeNode:
        if self.helper(root, 0, limit):
            return root
        else:
            return None