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

Source: leetcode | Difficulty: MEDIUM
Tags: Tree algorithms

Graph traversal

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


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):
		if root.left == None and root.right == None:
			self.maxdict[root] = self.sumdict[root]
		elif root.left and root.right:
			self.maxdict[root] = max(self.maxpathsum(root.left), self.maxpathsum(root.right))
		elif root.right:
			self.maxdict[root] = self.maxpathsum(root.right)
		else:
			self.maxdict[root] = self.maxpathsum(root.left)
		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)
		self.deletenodes(root, limit)
		if self.maxdict[root] < limit:
			return None
		else:
			return root


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)


class Solution:

	def sufficientSubset(self, root: TreeNode, limit: int) -> TreeNode:
		if root is None:
			return None
		print(root.val, limit)
		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


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
			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)

		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)

		def updateNode(node, s_node):
			if not node or not s_node.val:
				return None
			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)


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


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


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


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


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


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


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:
					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)
		return rtn


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


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


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


class Solution:

	def sufficientSubset(self, root: TreeNode, limit: int) -> TreeNode:

		def dfs(node, path_sum):
			if not node:
				return False
			path_sum += node.val
			if not node.left and (not node.right):
				return path_sum >= limit
			left = dfs(node.left, path_sum)
			right = dfs(node.right, path_sum)
			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


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


class Solution:

	def sufficientSubset(self, root: TreeNode, limit: int) -> TreeNode:
		if root == None:
			return None

		def dfs(root, val):
			if root == None:
				return (-10000000000.0, '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
				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


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:
		if node == None:
			return currentVal >= limit
		canLeft = self.validSubtree(node.left, limit, node.val + currentVal)
		canRight = self.validSubtree(node.right, limit, node.val + currentVal)
		if node.left and (not node.right):
			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


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