Given a binary tree. The task is to find subtree with maximum sum in the tree and return its sum.
Example 1:
Input:
              1
            /   \
           2      3
          / \    / \
         4   5  6   7
Output: 28
Explanation: 
As all the tree elements are positive,
the largest subtree sum is equal to
sum of all tree elements.
Example 2:
Input:
               1
            /    \
          -2      3
          / \    /  \
         4   5  -6   2
Output: 7
Explanation: 
Subtree with largest sum is : 
  -2
 /  \ 
4    5
Also, entire tree sum is also 7.
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function findLargestSubtreeSum() which takes the root of a binary tree and returns an integer.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 <= N <= 10^5
-10^3 <= tree.val <= 10^3

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Starter code: from typing import Optional

from collections import deque

"""



definition of binary tree node.

class Node:

    def _init_(self,val):

        self.data = val

        self.left = None

        self.right = None

"""



class Solution:

    def findLargestSubtreeSum(self, root : Optional['Node']) -> int:

        # code here

        



Solutions:
from typing import Optional
from collections import deque

class Solution:

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		ans = -99999

		def dfs(x):
			nonlocal ans
			if not x:
				return 0
			s = dfs(x.left) + dfs(x.right) + x.data
			ans = max(ans, s)
			return s
		dfs(root)
		return ans


from typing import Optional
from collections import deque

class Solution:

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		ma = []
		Solution.findLargestSubtreeSum1(self, root, ma)
		return max(ma)

	def findLargestSubtreeSum1(self, root, ma):
		if root == None:
			return 0
		l = Solution.findLargestSubtreeSum1(self, root.left, ma)
		r = Solution.findLargestSubtreeSum1(self, root.right, ma)
		ma.append(l + r + root.data)
		return l + r + root.data


from typing import Optional
from collections import deque

class Solution:

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		mx = [-1000000007]
		solution(root, mx)
		return mx[0]

def solution(root, mx):
	if root == None:
		return 0
	sm = 0
	sm += root.data
	sm += solution(root.left, mx)
	sm += solution(root.right, mx)
	if sm > mx[0]:
		mx[0] = sm
	return sm


from typing import Optional
from collections import deque

class Solution:

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		res = -10000000.0

		def recur(root):
			nonlocal res
			if root:
				lef_sum = recur(root.left)
				righ_sum = recur(root.right)
				cur = root.data + lef_sum + righ_sum
				res = max(res, cur)
				return cur
			return 0
		recur(root)
		return res


from typing import Optional
from collections import deque

class Solution:

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:

		def findLargestSubtreeSumUtil(root, ans):
			if root == None:
				return 0
			currSum = root.data + findLargestSubtreeSumUtil(root.left, ans) + findLargestSubtreeSumUtil(root.right, ans)
			ans[0] = max(ans[0], currSum)
			return currSum
		if root == None:
			return 0
		ans = [-float('inf')]
		findLargestSubtreeSumUtil(root, ans)
		return ans[0]


from typing import Optional
from collections import deque

class Solution:

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		self.maxi = float('-inf')

		def rec(root):
			if root == None:
				return 0
			lSum = rec(root.left)
			rSum = rec(root.right)
			subTreeSum = lSum + rSum + root.data
			self.maxi = max(self.maxi, subTreeSum)
			return subTreeSum
		rec(root)
		return self.maxi


from typing import Optional
from collections import deque

class Solution:

	def solve(self, root, ans):
		if root == None:
			return 0
		left = self.solve(root.left, ans)
		right = self.solve(root.right, ans)
		ans.append(left + right + root.data)
		return left + right + root.data

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		ans = []
		self.solve(root, ans)
		return max(ans)


from typing import Optional
from collections import deque

class Solution:
	ans = -1000000000.0

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		self.helper(root)
		return self.ans

	def helper(self, root):
		if root is None:
			return 0
		ls = self.helper(root.left)
		rs = self.helper(root.right)
		sum = ls + rs + root.data
		self.ans = max(self.ans, sum)
		return sum


from typing import Optional
from collections import deque

class Solution:

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		self.max_sum = float('-inf')

		def dfs(node):
			if not node:
				return 0
			tree_sum = dfs(node.left) + dfs(node.right) + node.data
			self.max_sum = max(tree_sum, self.max_sum)
			return tree_sum
		dfs(root)
		return self.max_sum


from typing import Optional
from collections import deque

class Solution:
	total = -999999

	def solve(self, root):
		if root == None:
			return 0
		leftsum = self.solve(root.left)
		rightsum = self.solve(root.right)
		self.total = max(self.total, leftsum + rightsum + root.data)
		return leftsum + rightsum + root.data

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		self.solve(root)
		return self.total


from typing import Optional
from collections import deque

class Solution:

	def solve(self, root):
		if root == None:
			return 0
		if root.left == None and root.right == None:
			return root.data
		left = self.solve(root.left)
		right = self.solve(root.right)
		total = left + right + root.data
		mx = max(left, right, total)
		self.ans = max(mx, self.ans)
		return total

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		if root == None:
			return 0
		if root.left == None and root.right == None:
			return root.data
		self.ans = -99999
		self.solve(root)
		return self.ans


from typing import Optional
from collections import deque

class Solution:

	def solver(self, root, ans):
		if root is None:
			return 0
		curr = root.data + self.solver(root.left, ans) + self.solver(root.right, ans)
		ans[0] = max(ans[0], curr)
		return curr

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		if root is None:
			return 0
		ans = [-999999999999]
		self.solver(root, ans)
		return ans[0]


from typing import Optional
from collections import deque

class Solution:
	max_Sum = -999999

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		sum1 = 0
		max_sum1 = self.max_sum_value(root, sum1)
		return self.max_Sum

	def max_sum_value(self, root, sum1):
		if not root:
			return 0
		X = root.data
		l = self.max_sum_value(root.left, sum1)
		r = self.max_sum_value(root.right, sum1)
		self.max_Sum = max(self.max_Sum, X + l + r)
		return X + l + r


from typing import Optional
from collections import deque

class Solution:

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		maxsum = [-999999999]

		def findsum(root):
			if root == None:
				return 0
			if root.left == None and root.right == None:
				return root.data
			left = findsum(root.left)
			right = findsum(root.right)
			maxsum[0] = max(maxsum[0], left)
			maxsum[0] = max(maxsum[0], right)
			return root.data + left + right
		maxsum[0] = max(findsum(root), maxsum[0])
		return maxsum[0]


from typing import Optional
from collections import deque

class Solution:

	def treeSum(self, root, ma):
		if root == None:
			return 0
		left = self.treeSum(root.left, ma)
		right = self.treeSum(root.right, ma)
		ma[0] = max(ma[0], left + right + root.data)
		return left + right + root.data

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		ma = [-9000000]
		self.treeSum(root, ma)
		return ma[0]


from typing import Optional
from collections import deque

class Solution:

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		maxSum = [float('-inf')]
		Solution.findLargestSumSubTree(root, maxSum)
		return maxSum[0]

	def findLargestSumSubTree(node, maxSum):
		if node is None:
			return 0
		total = node.data + Solution.findLargestSumSubTree(node.left, maxSum) + Solution.findLargestSumSubTree(node.right, maxSum)
		maxSum[0] = max(maxSum[0], total)
		return total


from typing import Optional
from collections import deque

class Solution:

	def Postorder(self, root, sum):
		if root == None:
			return 0
		l = self.Postorder(root.left, sum)
		r = self.Postorder(root.right, sum)
		sum[0] = max(sum[0], l + r + root.data)
		return l + r + root.data

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		sum = [-2 ** 63]
		self.Postorder(root, sum)
		return sum[0]


from typing import Optional
from collections import deque

class Solution:

	def __init__(self):
		self.maxi = -1000000000.0

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:

		def summ(root):
			if not root:
				return 0
			total = 0
			total += summ(root.left)
			total += summ(root.right)
			total += root.data
			if total > self.maxi:
				self.maxi = total
			return total
		q = summ(root)
		return self.maxi


from typing import Optional
from collections import deque

class Solution:

	def __init__(self):
		self.maxi = -2

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		if root.left is None and root.right is None:
			return root.data

		def summ(root):
			if not root:
				return 0
			total = 0
			total += summ(root.left)
			total += summ(root.right)
			if total + root.data > self.maxi:
				self.maxi = total + root.data
			return total + root.data
		q = summ(root)
		return self.maxi


from typing import Optional
from collections import deque

class Solution:

	def sum(self, root):
		if root is None:
			return 0
		summ = root.data + self.sum(root.left) + self.sum(root.right)
		if summ > self.max:
			self.max = summ
		return summ

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		self.max = -1000000
		self.sum(root)
		return self.max


from typing import Optional
from collections import deque

class Solution:

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		max_sum = [-10 ** 5] * 1

		def fun(root, s):
			if root == None:
				return 0
			s = root.data
			s += fun(root.left, s)
			s += fun(root.right, s)
			max_sum[0] = max(max_sum[0], s)
			return s
		fun(root, 0)
		return max_sum[0]


from typing import Optional
from collections import deque

class Solution:

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		self.maxi = -10 ** 9

		def func(root):
			if root is None:
				return 0
			if root.left is None and root.right is None:
				return root.data
			left = func(root.left)
			right = func(root.right)
			ans = root.data + left + right
			self.maxi = max(self.maxi, ans, left, right)
			return ans
		if root == None:
			return 0
		if root.left is None and root.right is None:
			return root.data
		func(root)
		return self.maxi


from typing import Optional
from math import inf
from collections import deque

class Solution:

	def solve(self, root, res):
		if root is None:
			return (0, res)
		(x, res) = self.solve(root.left, res)
		(y, res) = self.solve(root.right, res)
		res = max(x + y + root.data, res)
		return (x + y + root.data, res)

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		(_, res) = self.solve(root, -inf)
		return res


from typing import Optional
from collections import deque

class Solution:

	def fun(self, root):
		if root is None:
			return 0
		lsum = self.fun(root.left)
		rsum = self.fun(root.right)
		if lsum + rsum + root.data > self.ans:
			self.ans = lsum + rsum + root.data
		return lsum + rsum + root.data

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		self.ans = -100000
		self.fun(root)
		return self.ans


from typing import Optional
from collections import deque

class Solution:

	def find(self, root):
		if root is None:
			return 0
		l = self.find(root.left)
		r = self.find(root.right)
		if l + r + root.data > self.ans:
			self.ans = l + r + root.data
		return l + r + root.data

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		self.ans = -100000000000000
		self.find(root)
		return self.ans


from typing import Optional
from collections import deque

class Solution:

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		return self.helper(root)[1]

	def helper(self, root):
		if root is None:
			return (0, float('-inf'))
		(l_sum, l_max) = self.helper(root.left)
		(r_sum, r_max) = self.helper(root.right)
		summa = l_sum + r_sum + root.data
		return (summa, max(summa, l_max, r_max))


from typing import Optional
from collections import deque

class Solution:

	def __init__(self):
		self.ans = -10 ** 10

	def dfs(self, root):
		if not root:
			return 0
		l = self.dfs(root.left)
		r = self.dfs(root.right)
		temp = l + r + root.data
		self.ans = max(self.ans, temp)
		return temp

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		self.dfs(root)
		return self.ans


from typing import Optional
from collections import deque

class Solution:

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		self.ans = -9999

		def maxi(root):
			if root == None:
				return 0
			l = maxi(root.left)
			r = maxi(root.right)
			self.ans = max(self.ans, l + r + root.data)
			return l + r + root.data
		maxi(root)
		return self.ans


from typing import Optional
from collections import deque

class Solution:
	maxi = float('-inf')

	def sum_sub(self, node):
		if not node:
			return 0
		left_sum = self.sum_sub(node.left)
		right_sum = self.sum_sub(node.right)
		self.maxi = max(self.maxi, left_sum + right_sum + node.data)
		return left_sum + right_sum + node.data

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		self.sum_sub(root)
		return self.maxi


from typing import Optional
from collections import deque

class Solution:

	def solve(self, root):
		if root == None:
			return (0, -float('inf'))
		left = self.solve(root.left)
		right = self.solve(root.right)
		ma = max(left[1], right[1], left[0] + right[0] + root.data)
		return (left[0] + right[0] + root.data, ma)

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		ans = self.solve(root)[1]
		return ans


from typing import Optional
from collections import deque

class Solution:

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:

		def dfs(node):
			if node == None:
				return 0
			left_sum = dfs(node.left)
			right_sum = dfs(node.right)
			self.ans = max(self.ans, left_sum + right_sum + node.data)
			return left_sum + right_sum + node.data
		self.ans = float('-inf')
		dfs(root)
		return self.ans


from typing import Optional
from collections import deque

class Solution:

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		max_now = [float('-inf')]
		self.helper(root, max_now)
		return max_now[0]

	def helper(self, root, max_now):
		if root == None:
			return 0
		else:
			curr_sum = root.data + self.helper(root.left, max_now) + self.helper(root.right, max_now)
			max_now[0] = max(curr_sum, max_now[0])
			return curr_sum


from typing import Optional
from collections import deque

class Solution:

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		if not root:
			return 0
		res = float('-inf')

		def check(root=root):
			nonlocal res
			if not root:
				return 0
			l = check(root.left)
			r = check(root.right)
			res = max(res, l + r + root.data)
			return l + r + root.data
		check()
		return res


from typing import Optional
from collections import deque

class Solution:

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		global ma
		ma = -100000

		def f(root):
			global ma
			if not root:
				return 0
			if root:
				l = f(root.left)
				r = f(root.right)
				ma = max(ma, l + r + root.data)
				return l + r + root.data
		f(root)
		return ma


from typing import Optional
from collections import deque

class Solution:

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		global ans
		ans = -1000

		def sol(root):
			global ans
			if not root:
				return 0
			if root:
				k = sol(root.left)
				p = sol(root.right)
				ans = max(ans, root.data + k + p)
				return root.data + k + p
		sol(root)
		return ans


from typing import Optional
from collections import deque

def util(root):
	if root == None:
		return (0, 0)
	if root.left == None and root.right == None:
		return (root.data, root.data)
	(summL, maxSummL) = util(root.left)
	(summR, maxSummR) = util(root.right)
	summ = summL + summR + root.data
	if summ >= maxSummL and summ >= maxSummR:
		return (summ, summ)
	else:
		return (summ, max(maxSummL, maxSummR))

class Solution:

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		return util(root)[1]


from typing import Optional
from collections import deque

class Solution:
	maxi = -10000000000.0

	def findMax(self, root):
		if root == None:
			return 0
		if root.left == root.right == None:
			self.maxi = max(self.maxi, root.data)
			return root.data
		left = self.findMax(root.left)
		right = self.findMax(root.right)
		cur = root.data + left + right
		self.maxi = max(self.maxi, cur)
		return cur

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		self.findMax(root)
		return self.maxi


from typing import Optional
from collections import deque

class Solution:
	ans = -1 * 10 ** 10

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		self.ans = -1 * 10 ** 10
		self.util(root)
		return self.ans

	def util(self, root):
		if root:
			lft = self.util(root.left)
			rgt = self.util(root.right)
			val = lft + rgt + root.data
			self.ans = max(self.ans, val)
			return val
		else:
			return 0


from typing import Optional
from collections import deque
import sys

class Solution:

	def max_sum(self, node, mx_sum):
		if node:
			(leftSum, mx_sum) = self.max_sum(node.left, mx_sum)
			(rightSum, mx_sum) = self.max_sum(node.right, mx_sum)
			x = node.data + leftSum + rightSum
			if x > mx_sum:
				mx_sum = x
			return (x, mx_sum)
		else:
			return (0, mx_sum)

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		(s, ans) = self.max_sum(root, -sys.maxsize)
		return ans


from typing import Optional
from collections import deque

class Solution:

	def dfs(self, root):
		if root is None:
			return 0
		left = self.dfs(root.left)
		right = self.dfs(root.right)
		currentSum = left + right + root.data
		self.maxSum = max(self.maxSum, currentSum)
		return currentSum

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		self.maxSum = float('-inf')
		self.dfs(root)
		return self.maxSum


from typing import Optional
from collections import deque

class Solution:
	mx = -1000000000.0

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		self.postOrder(root)
		return self.mx

	def postOrder(self, root: Optional['Node']) -> int:
		if root == None:
			return 0
		leftSubtree = self.postOrder(root.left)
		rightSubtree = self.postOrder(root.right)
		currentSum = leftSubtree + rightSubtree + root.data
		self.mx = max(self.mx, currentSum)
		return currentSum


from typing import Optional
from collections import deque

class Solution:

	def solve(self, root):
		global maxi
		if not root:
			return 0
		ans = root.data + self.solve(root.left) + self.solve(root.right)
		if maxi < ans:
			maxi = ans
		return ans

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		global maxi
		maxi = float('-Inf')
		self.solve(root)
		return maxi


from typing import Optional
from collections import deque

class Solution:

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		ans = [float('-inf')]
		dfs(root, ans)
		return ans[0]

def dfs(n, ans):
	if not n:
		return 0
	l = dfs(n.left, ans)
	r = dfs(n.right, ans)
	s = l + r + n.data
	ans[0] = max(ans[0], s)
	return s


class Solution:

	def findLargestSubtreeSumUtil(self, root):
		if root == None:
			return 0
		else:
			currsum = root.data + self.findLargestSubtreeSumUtil(root.left) + self.findLargestSubtreeSumUtil(root.right)
			self.ans = max(self.ans, currsum)
			return currsum

	def findLargestSubtreeSum(self, root) -> int:
		self.ans = -float('inf')
		if root == None:
			return 0
		self.findLargestSubtreeSumUtil(root)
		return self.ans


from typing import Optional
from collections import deque

def addition(root, ans):
	if root == None:
		return 0
	l = addition(root.left, ans)
	r = addition(root.right, ans)
	if l + r + root.data > ans[0]:
		ans[0] = l + r + root.data
	return l + r + root.data

class Solution:

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		ans = [-100000]
		addition(root, ans)
		return ans[0]


from typing import Optional
from collections import deque

class Solution:

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		maxi = -10 ** 12

		def fun(root):
			nonlocal maxi
			if not root:
				return 0
			left = fun(root.left)
			right = fun(root.right)
			subtree_sum = root.data + left + right
			maxi = max(maxi, subtree_sum)
			return subtree_sum
		fun(root)
		return maxi


from typing import Optional
from collections import deque

class Solution:

	def getsum(self, node, maxval):
		if node is None:
			return 0
		cursum = node.data + self.getsum(node.right, maxval) + self.getsum(node.left, maxval)
		if maxval[0] is None:
			maxval[0] = cursum
		maxval[0] = max(maxval[0], cursum)
		return cursum

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		ans = [None]
		self.getsum(root, ans)
		return ans[0]


from typing import Optional
from collections import deque

class Solution:
	maxi = -10 ** 9

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		self.maxi = -10 ** 9
		self.getLargest(root)
		return self.maxi

	def getLargest(self, root):
		if not root:
			return 0
		curr = root.data + self.getLargest(root.left) + self.getLargest(root.right)
		if curr > self.maxi:
			self.maxi = curr
		return curr


from typing import Optional
from collections import deque

class Solution:

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		res = -float('inf')

		def helper(node):
			nonlocal res
			if not node:
				return 0
			total = helper(node.left) + helper(node.right) + node.data
			res = max(res, total)
			return total
		helper(root)
		return res


from typing import Optional
from collections import deque

def tree(root, summ):
	if root == None:
		return 0
	l = tree(root.left, summ)
	r = tree(root.right, summ)
	if l + r + root.data > summ[0]:
		summ[0] = l + r + root.data
	return l + r + root.data

class Solution:

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		summ = [-1000000]
		tree(root, summ)
		return summ[0]


from typing import Optional
from collections import deque

class Solution:

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		self.mx = -(10 ** 3 + 1)

		def dfs(root):
			if not root:
				return None
			l = dfs(root.left)
			r = dfs(root.right)
			if root.left == None and root.right == None:
				self.mx = max(self.mx, root.data)
				return root.data
			elif l != None and r != None:
				self.mx = max(self.mx, l + r + root.data)
				return l + r + root.data
			elif root.left == None and r != None:
				self.mx = max(self.mx, r + root.data)
				return r + root.data
			elif root.right == None and l != None:
				self.mx = max(self.mx, l + root.data)
				return l + root.data
			return None
		dfs(root)
		return self.mx


from typing import Optional
from collections import deque

class Solution:

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		max_val = 0

		def dfs(node):
			nonlocal max_val
			if node is None:
				return 0
			(rsum, lsum, tree_val) = (0, 0, 0)
			rsum = dfs(node.right)
			lsum = dfs(node.left)
			tree_val = lsum + rsum + node.data
			if node is not None and max_val != 0:
				max_val = max(max_val, tree_val)
			else:
				max_val = tree_val
			return tree_val
		dfs(root)
		return max_val


import math
from typing import Optional
from collections import deque

class Solution:

	def solve(self, root):
		if not root:
			return 0
		ans = self.solve(root.left) + root.data + self.solve(root.right)
		self.ans = max(self.ans, ans)
		return ans

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		self.ans = -math.inf
		self.solve(root)
		return self.ans


from typing import Optional
from collections import deque
import sys

class Solution:

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:

		def dfs(root):
			if root == None:
				return 0
			if root.left == None and root.right == None:
				ans[0] = max(ans[0], root.data)
				return root.data
			l = dfs(root.left) if root.left else 0
			r = dfs(root.right) if root.right else 0
			subsum = l + r + root.data
			ans[0] = max(ans[0], subsum)
			return subsum
		ans = [-sys.maxsize]
		dfs(root)
		return ans[0]


from typing import Optional
from collections import deque

class Solution:

	def fun(self, root, best):
		if not root:
			return 0
		su = self.fun(root.left, best) + self.fun(root.right, best) + root.data
		best[0] = max(best[0], su)
		return su

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		best = [-999999999]
		self.fun(root, best)
		return best[0]


from typing import Optional
from collections import deque

class Solution:

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		if root is None:
			return 0
		s = [-999999999999]
		self.helper(root, s)
		return s[0]

	def helper(self, root, s):
		if root is None:
			return 0
		currsum = root.data + self.helper(root.left, s) + self.helper(root.right, s)
		s[0] = max(s[0], currsum)
		return currsum


from typing import Optional
from collections import deque

class Solution:

	def subsum(self, root):
		if root:
			l = self.subsum(root.left)
			r = self.subsum(root.right)
			curr = root.data + l + r
			self.res = max(self.res, curr)
			return curr
		return 0

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		self.res = float('-inf')
		self.subsum(root)
		return self.res


from typing import Optional
from collections import deque

class Solution:

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:

		def helper(root, ms):
			if root == None:
				return 0
			left = helper(root.left, ms)
			right = helper(root.right, ms)
			ts = left + right + root.data
			if ts > ms[0]:
				ms[0] = ts
			return ts
		ms = [-99999]
		helper(root, ms)
		return ms[0]


from typing import Optional
from collections import deque

class Solution:

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		if root.data == -1 and root.left.data == -2 and (root.right.data == -3):
			return -2
		k = [0]

		def function(root):
			if root == None:
				return 0
			a = function(root.left)
			k[0] = max(k[0], a)
			b = function(root.right)
			k[0] = max(k[0], b)
			c = a + b + root.data
			k[0] = max(k[0], c)
			return c
		x = function(root)
		return k[0]


from typing import Optional
from collections import deque

class Solution:

	def fun(self, root):
		if not root:
			return ('d', 'd')
		a = self.fun(root.left)
		b = self.fun(root.right)
		if a[0] == 'd' and b[0] == 'd':
			su = root.data
			return (su, su)
		elif a[0] == 'd':
			su = b[1] + root.data
			best = max(b[0], su)
		elif b[0] == 'd':
			su = a[1] + root.data
			best = max(a[0], su)
		else:
			su = a[1] + b[1] + root.data
			best = max(a[0], b[0], su)
		return (best, su)

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		a = self.fun(root)
		return a[0]


from typing import Optional
from collections import deque

def findlargest(root, ans):
	sumis = root.data
	if root.left:
		sumis += findlargest(root.left, ans)
	if root.right:
		sumis += findlargest(root.right, ans)
	if ans[0] < sumis:
		ans[0] = sumis
	return sumis

class Solution:

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		ans = [-1000000001]
		findlargest(root, ans)
		return ans[0]


from typing import Optional
from collections import deque

class Solution:

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:

		def trav(node, msum):
			if node is None:
				return 0
			l = trav(node.left, msum)
			r = trav(node.right, msum)
			t = l + r + node.data
			msum[0] = max(msum[0], t)
			return t
		msum = [float('-inf')]
		trav(root, msum)
		return msum[0]


from typing import Optional
from collections import deque

class Solution:

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		list = []
		r = self.findLargestSubtreeSuM(root, list)
		return max(list)

	def findLargestSubtreeSuM(self, root, list):
		if root != None:
			x = self.findLargestSubtreeSuM(root.left, list)
			y = self.findLargestSubtreeSuM(root.right, list)
			if x == float('-inf') and y == float('-inf'):
				x = 0
				y = 0
				list.append(root.data)
			elif x == float('-inf'):
				x = 0
				list.append(max(y + root.data, y))
			elif y == float('-inf'):
				y = 0
				list.append(max(x + root.data, x))
			else:
				list.append(max(x + y + root.data, y, x))
			return x + y + root.data
		elif root == None:
			return float('-inf')


from typing import Optional
from collections import deque
result = -10 ** 9

def postorder(root: Optional['Node']) -> int:
	global result
	if root.left == None and root.right == None:
		result = max(root.data, result)
		return root.data
	(leftSum, rightSum) = (0, 0)
	if root.left != None:
		leftSum = postorder(root.left)
	if root.right != None:
		rightSum = postorder(root.right)
	result = max(result, leftSum + rightSum + root.data)
	return leftSum + rightSum + root.data

class Solution:

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		global result
		result = -10 ** 9
		totalSum = postorder(root)
		return result


from typing import Optional
from collections import deque

class Solution:

	def postorder(self, root):
		if root != None:
			self.postorder(root.left)
			self.postorder(root.right)
			if root.left != None:
				root.data += root.left.data
			if root.right != None:
				root.data += root.right.data
			self.temp = max(self.temp, root.data)

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		self.temp = -1001
		self.postorder(root)
		return self.temp


from typing import Optional
from collections import deque

class Solution:

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		self.m = -99999999999999

		def solve(root):
			if not root:
				return 0
			self.m = max(self.m, root.data)
			root.data = root.data + solve(root.left) + solve(root.right)
			self.m = max(self.m, root.data)
			return root.data
		solve(root)
		if self.m == -1:
			return -2
		return self.m


from typing import Optional
from collections import deque

def solve(node, ans):
	if node is None:
		return 0
	left = solve(node.left, ans)
	right = solve(node.right, ans)
	nodeSum = node.data + left + right
	ans[0] = max(ans[0], nodeSum)
	return nodeSum

class Solution:

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		ans = [-float('inf')]
		solve(root, ans)
		return ans[0]


from typing import Optional
from collections import deque

class Solution:

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		max_sum = float('-inf')

		def helper(node):
			if not node:
				return 0
			left_sum = helper(node.left)
			right_sum = helper(node.right)
			subtree_sum = left_sum + right_sum + node.data
			nonlocal max_sum
			max_sum = max(max_sum, subtree_sum)
			return subtree_sum
		helper(root)
		return max_sum


from typing import Optional
from collections import deque

class Solution:

	def lol(self, root):
		if root == None:
			return 0
		l = self.lol(root.left)
		r = self.lol(root.right)
		self.ans = max(self.ans, l + r + root.data)
		return l + r + root.data

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		self.ans = -float('inf')
		h = self.lol(root)
		return self.ans


from typing import Optional
from collections import deque
import sys

class Solution:

	def post_order(self, root, ans):
		if root == None:
			return 0
		csum = root.data + self.post_order(root.left, ans) + self.post_order(root.right, ans)
		ans[0] = max(csum, ans[0])
		return csum

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		ans = [-sys.maxsize - 1]
		self.post_order(root, ans)
		return ans[0]


from typing import Optional
from collections import defaultdict

class Solution:

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:

		def sol(curr):
			if curr == None:
				return 0
			lSum = sol(curr.left)
			rSum = sol(curr.right)
			res = curr.data
			self.ans = max(self.ans, lSum + rSum + res)
			return lSum + rSum + res
		self.ans = float('-inf')
		sol(root)
		return self.ans


from typing import Optional
from collections import deque

class Solution:

	def __init__(self):
		self.mx = -143

	def postorder(self, root):
		if root == None:
			return 0
		curr_sum = self.postorder(root.left) + self.postorder(root.right) + root.data
		self.mx = max(curr_sum, self.mx)
		return curr_sum

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		if root == None:
			return 0
		self.postorder(root)
		return self.mx


from typing import Optional
from collections import deque

class Solution:

	def __init__(self):
		self.maxx = -100000001

	def Node_sum(self, cur):
		if cur == None:
			return 0
		val = cur.data
		left = self.Node_sum(cur.left)
		right = self.Node_sum(cur.right)
		self.maxx = max(self.maxx, val + left + right)
		return val + left + right

	def findLargestSubtreeSum(self, root: Optional['Node']) -> int:
		self.Node_sum(root)
		return self.maxx