Given a binary tree, the task is to find the maximum path sum. The path may start and end at any node in the tree.
Example 1:
Input:
     10
    /  \
   2   -25
  / \  /  \
 20 1  3  4
Output: 32
Explanation: Path in the given tree goes
like 10 , 2 , 20 which gives the max
sum as 32.
Example 2:
Input:
     10
   /    \
  2      5
          \
          -2
Output: 17
Explanation: Path in the given tree goes
like 2 , 10 , 5 which gives the max sum
as 17.
Your Task:
You don't need to take input or print anything. Your task is to complete the function findMaxSum() that takes root as input and returns max sum between any two nodes in the given Binary Tree.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(Height of the Tree).
Constraints:
1 ≤ Number of nodes ≤ 10^{3}
1 ≤ |Data on node| ≤ 10^{4}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3


'''
class Node:
    def __init__(self,val):
        self.data = val
        self.left = None
        self.right = None
'''

class Solution:
    #Function to return maximum path sum from any node in a tree.
    def findMaxSum(self, root): 
        #Your code here

Solutions:
class Solution:

	def maxPathSum(self, root, maxSum):
		if not root:
			return 0
		leftSum = max(0, Solution.maxPathSum(self, root.left, maxSum))
		rightSum = max(0, Solution.maxPathSum(self, root.right, maxSum))
		maxSum[0] = max(maxSum[0], leftSum + rightSum + root.data)
		return root.data + max(leftSum, rightSum)

	def findMaxSum(self, root):
		maxSum = [-1000000000.0]
		Solution.maxPathSum(self, root, maxSum)
		return maxSum[0]


class Solution:

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

	def findMaxSum(self, root):
		self.res = float('-inf')
		self.solve(root)
		return self.res


import sys

class Solution:

	def util(self, root):
		global ans
		if root == None:
			return -sys.maxsize
		l = self.util(root.left)
		r = self.util(root.right)
		ans = max(ans, max(l + r + root.data, max(r + root.data, max(root.data, l + root.data))))
		if l > 0 or r > 0:
			return max(l + root.data, r + root.data)
		else:
			return root.data

	def findMaxSum(self, root):
		global ans
		ans = -sys.maxsize
		self.util(root)
		return ans


class Solution:

	def findMaxSum(self, root):
		maxPath = [-sys.maxsize - 1]

		def maxSum(node, path):
			if not node:
				return 0
			ls = max(0, maxSum(node.left, path))
			rs = max(0, maxSum(node.right, path))
			path[0] = max(path[0], ls + rs + node.data)
			return max(ls, rs) + node.data
		maxSum(root, maxPath)
		return maxPath[0]


class Solution:

	def findMaxSum(self, root):
		res = [root.data]

		def dfs(root):
			if root == None:
				return 0
			leftmax = dfs(root.left)
			rightmax = dfs(root.right)
			leftmax = max(leftmax, 0)
			rightmax = max(rightmax, 0)
			res[0] = max(res[0], root.data + leftmax + rightmax)
			return root.data + max(leftmax, rightmax)
		dfs(root)
		return res[0]


class Solution:

	def findMaxSum(self, root):
		self.maxs = float('-inf')
		self.maxSum(root, self.maxs)
		return self.maxs

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


class Solution:

	def findMaxSum(self, root):

		def solve(root):
			nonlocal maxi
			if root is None:
				return 0
			leftsum = max(solve(root.left), 0)
			rightsum = max(solve(root.right), 0)
			maxi = max(maxi, leftsum + rightsum + root.data)
			return root.data + max(leftsum, rightsum)
		maxi = -float('inf')
		solve(root)
		return maxi


class Solution:

	def findMaxSum(self, root):
		if not root:
			return -float('inf')
		return max(root.data + self.sumfromRoot(root.left) + self.sumfromRoot(root.right), self.findMaxSum(root.left), self.findMaxSum(root.right))

	def sumfromRoot(self, root):
		if not root:
			return 0
		else:
			return max(0, root.data + max(self.sumfromRoot(root.left), self.sumfromRoot(root.right)))


class Solution:

	def __init__(self):
		self.sum = float('-inf')

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

	def findMaxSum(self, root):
		s = self.recursive(root)
		return max(self.sum, s)


class Solution:

	def findMaxSum(self, root):
		max_path = [float('-inf')]

		def dfs(root):
			if not root:
				return 0
			max_l = dfs(root.left)
			max_r = dfs(root.right)
			max_l = max(max_l, 0)
			max_r = max(max_r, 0)
			curr_max = max_l + max_r + root.data
			max_path[0] = max(max_path[0], curr_max)
			return root.data + max(max_l, max_r)
		dfs(root)
		return max_path[0]


class Solution:

	def solve(self, root, res):
		if root is None:
			return 0
		l = self.solve(root.left, res)
		r = self.solve(root.right, res)
		temp = max(max(l, r) + root.data, root.data)
		ans = max(temp, l + r + root.data)
		res[0] = max(ans, res[0])
		return temp

	def findMaxSum(self, root):
		res = [-10000000000]
		self.solve(root, res)
		return res[0]


def fun(root):
	if root is None:
		return 0
	l = fun(root.left)
	r = fun(root.right)
	max_sig = max(max(l, r) + root.data, root.data)
	max_top = max(max_sig, l + r + root.data)
	fun.res = max(fun.res, max_top)
	return max_sig

class Solution:

	def findMaxSum(self, root):
		fun.res = float('-inf')
		fun(root)
		return fun.res


class Solution:

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

	def findMaxSum(self, root):
		self.ans = float('-inf')
		self.max_path_sum(root, self.ans)
		return self.ans


class Solution:

	def findMaxSum(self, root):
		largestSum = float('-inf')

		def maxSum(root):
			nonlocal largestSum
			if root is None:
				return 0
			leftSum = max(0, maxSum(root.left))
			rightSum = max(0, maxSum(root.right))
			largestSum = max(largestSum, leftSum + rightSum + root.data)
			return root.data + max(leftSum, rightSum)
		maxSum(root)
		return largestSum


class Solution:

	def findMaxSum(self, root):
		if not root:
			return -float('inf')
		return max(root.data, root.data + self.height(root.left) + self.height(root.right), self.findMaxSum(root.left), self.findMaxSum(root.right))

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


class Solution:

	def findMaxSum(self, root):
		ans = [root.data]

		def path(root1):
			if root1 == None:
				return 0
			ls = max(0, path(root1.left))
			rs = max(0, path(root1.right))
			ans[0] = max(ans[0], root1.data + ls + rs)
			return root1.data + max(ls, rs)
		path(root)
		return ans[0]