Given a binary tree in which each node element contains a number. Find the maximum possible path sum from one special node to another special node.
Note: Here special node is a node which is connected to exactly one different node.
Example 1:
Input:      
           3                               
         /    \                          
       4       5                     
      /  \      
    -10   4                          
Output: 16
Explanation:
Maximum Sum lies between special node 4 and 5.
4 + 4 + 3 + 5 = 16.
Example 2:
Input:    
            -15                               
         /      \                          
        5         6                      
      /  \       / \
    -8    1     3   9
   /  \              \
  2   -3              0
                     / \
                    4  -1
                       /
                     10  
Output:  27
Explanation:
The maximum possible sum from one special node 
to another is (3 + 6 + 9 + 0 + -1 + 10 = 27)
Your Task:  
You dont need to read input or print anything. Complete the function maxPathSum() which takes root node as input parameter and returns the maximum sum between 2 special nodes.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(Height of Tree)
Constraints:
2  ≤  Number of nodes  ≤  10^{4}
-10^{3  }≤ Value of each node ≤ 10^{3}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3



'''

# Node Class:

class Node:

    def _init_(self,val):

        self.data = val

        self.left = None

        self.right = None

        '''

class Solution:        

    def maxPathSum(self, root):

        # code here

Solutions:
class Solution:

	def maxPathSum(self, root):
		mx = float('-inf')

		def maxsum(r):
			nonlocal mx
			if not r:
				return float('-inf')
			if not r.left and (not r.right):
				return r.data
			l = maxsum(r.left)
			ri = maxsum(r.right)
			mx = max(mx, l + ri + r.data)
			return r.data + max(l, ri)
		y = maxsum(root)
		if not root.left or not root.right:
			return max(y, mx)
		return mx


class Solution:

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

	def maxPathSum(self, root):
		self.res = float('-inf')
		a = self.solve(root)
		if root.left == None or root.right == None:
			return max(a, self.res)
		return self.res


class Solution:

	def maxPathSum(self, root):
		self.max_sum = -10 ** 6 + 1
		head = root

		def diameter(root):
			left = -10 ** 6 + 1
			right = -10 ** 6 + 1
			if root.left == None and root.right == None:
				return root.data
			elif root.left == None:
				right = diameter(root.right)
			elif root.right == None:
				left = diameter(root.left)
			else:
				left = diameter(root.left)
				right = diameter(root.right)
			path = max(left, right) + root.data
			value = root.data
			if root == head and left == -10 ** 6 + 1:
				value += right
			elif root == head and right == -10 ** 6 + 1:
				value += left
			else:
				value += left + right
			self.max_sum = max(self.max_sum, value)
			return path
		diameter(root)
		return self.max_sum


class Solution:

	def maxTree(self, root, head):
		if root == None:
			return -10000000
		if root.left == None and root.right == None:
			return root.data
		global ans
		left = self.maxTree(root.left, head)
		right = self.maxTree(root.right, head)
		ans = max(ans, root.data + left + right)
		if root == head and (root.left == None or root.right == None):
			ans = max(ans, root.data + max(left, right))
		return root.data + max(left, right)

	def maxPathSum(self, root):
		global ans
		ans = -10000000
		self.maxTree(root, root)
		return ans


class Solution:

	def maxPathSum(self, root):

		def find(root, ans):
			if root is None:
				return 0
			left = find(root.left, ans)
			right = find(root.right, ans)
			if root.left and root.right:
				ans[0] = max(ans[0], left + right + root.data)
				return max(left, right) + root.data
			if root.left:
				val = left + root.data
				return val
			if root.right:
				val = right + root.data
				return val
			return root.data
		ans = [-99999999]
		h = find(root, ans)
		if root.left and root.right:
			return ans[0]
		return max(h, ans[0])


class Solution:
	res = -999999999

	def maxPathSumUtil(self, root):
		global res
		if root is None:
			return 0
		if root.left is None and root.right is None:
			return root.data
		ls = self.maxPathSumUtil(root.left)
		rs = self.maxPathSumUtil(root.right)
		if root.left and root.right:
			res = max(res, ls + rs + root.data)
			return max(ls, rs) + root.data
		if root.left is None:
			return rs + root.data
		else:
			return ls + root.data

	def maxPathSum(self, root):
		global res
		res = -999999999
		h = self.maxPathSumUtil(root)
		if root.left is None:
			res = max(res, h)
		if root.right is None:
			res = max(res, h)
		return res


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def dfs(self, root, ans, tmp):
		if not root:
			return float('-inf')
		left_node = self.dfs(root.left, ans, tmp)
		right_node = self.dfs(root.right, ans, tmp)
		if root == tmp:
			left_node = 0 if left_node == float('-inf') else left_node
			right_node = 0 if right_node == float('-inf') else right_node
			ans[0] = max(ans[0], left_node + root.data + right_node)
		elif root.left and root.right:
			ans[0] = max(ans[0], left_node + root.data + right_node)
		return root.data + (0 if max(left_node, right_node) == float('-inf') else max(left_node, right_node))

	def maxPathSum(self, root):
		ans = [float('-inf')]
		self.dfs(root, ans, root)
		return ans[0]


class Solution:

	def dfs(self, root, ans, rt):
		if not root:
			return float('-inf')
		l = self.dfs(root.left, ans, rt)
		r = self.dfs(root.right, ans, rt)
		if root == rt:
			l = 0 if l == float('-inf') else l
			r = 0 if r == float('-inf') else r
			ans[0] = max(ans[0], l + root.data + r)
		elif root.left and root.right:
			ans[0] = max(ans[0], l + root.data + r)
		return root.data + (0 if max(l, r) == float('-inf') else max(l, r))

	def maxPathSum(self, root):
		ans = [float('-inf')]
		self.dfs(root, ans, root)
		return ans[0]


class Solution:

	def solve(self, root):
		if root == None:
			return 0
		if root.left == None and root.right == None:
			return root.data
		l = self.solve(root.left)
		r = self.solve(root.right)
		if root.left == None:
			return r + root.data
		elif root.right == None:
			return l + root.data
		else:
			self.mx = max(self.mx, l + root.data + r)
			return max(l, r) + root.data

	def maxPathSum(self, root):
		self.mx = -1000000000
		res = self.solve(root)
		if root.left == None or root.right == None:
			return max(res, self.mx)
		else:
			return self.mx


class Solution:

	def maxPathSum(self, root):

		def maxPath(root):
			if not root:
				return 0
			if root.left == None and root.right == None:
				return root.data
			left = maxPath(root.left)
			right = maxPath(root.right)
			if root.left == None:
				return root.data + right
			if root.right == None:
				return root.data + left
			self.maxSum = max(self.maxSum, left + right + root.data)
			return max(left + root.data, right + root.data)
		if not root:
			return 0
		if root.left == None and root.right == None:
			return root.data
		self.maxSum = -float('inf')
		x = maxPath(root)
		if root.left == None or root.right == None:
			return max(self.maxSum, x)
		return self.maxSum


max_ = -10 ** 7 - 1

class Solution:

	def maxPathSum(self, head):
		global max_
		a = [0, 0]
		self.maxPath(head)
		if head.left and (not head.right):
			self.create(head)
			max_ = max(max_, head.data)
		elif not head.left and head.right:
			self.create(head)
			max_ = max(max_, head.data)
		a1 = max_
		max_ = -10 ** 7 - 1
		return a1

	def create(self, head):
		if not head:
			return
		self.create(head.left)
		self.create(head.right)
		if not head.left and (not head.right):
			return
		a = head.left.data if head.left else -10 ** 7 - 1
		b = head.right.data if head.right else -10 ** 7 - 1
		head.data += max(a, b)

	def maxPath(self, root):
		global max_
		if not root:
			return 0
		l = -10 ** 7 - 1 if not root.left else self.maxPath(root.left)
		r = self.maxPath(root.right) if root.right else -10 ** 7 - 1
		if not root.left and (not root.right):
			return root.data
		max_ = max(max_, l + r + root.data)
		return max(l, r) + root.data


class Solution:

	def maxPathSum(self, root):
		maxpath = -100000001

		def getpath(node, maxpath):
			reclen = node.data
			if node.left:
				(leftlen, maxpath) = getpath(node.left, maxpath)
				reclen += leftlen
			if node.right:
				(rightlen, maxpath) = getpath(node.right, maxpath)
				reclen += rightlen
			if node.left and node.right:
				maxpath = max(maxpath, node.data + leftlen + rightlen)
				reclen = node.data + max(leftlen, rightlen)
			return (reclen, maxpath)
		if root.left:
			(leftpath, maxpath) = getpath(root.left, maxpath)
		if root.right:
			(rightpath, maxpath) = getpath(root.right, maxpath)
			if root.left:
				maxpath = max(leftpath + root.data + rightpath, maxpath)
		if root.left and (not root.right):
			maxpath = max(leftpath + root.data, maxpath)
		elif not root.left and root.right:
			maxpath = max(rightpath + root.data, maxpath)
		return maxpath


class Solution:

	def maxPathSum(self, root):
		res = float('-inf')
		ans = float('-inf')

		def getMax(node, s):
			nonlocal res
			nonlocal ans
			if not node:
				return 0
			else:
				left = getMax(node.left, s)
				right = getMax(node.right, s)
				if not node.left and (not node.right):
					return node.data
				if not node.left:
					if node == s:
						res = max(res, right + node.data)
					return node.data + right
				if not node.right:
					if node == s:
						res = max(res, left + node.data)
					return node.data + left
				res = max(res, left + right + node.data)
				return node.data + max(left, right)
		getMax(root, root)
		return res


class Solution:

	def maxPathSum(self, root):
		l = [-999999]

		def fun(root):
			if root == None:
				return 0
			if root.left == None and root.right == None:
				return root.data
			lh = fun(root.left)
			rh = fun(root.right)
			if root.left != None and root.right != None:
				l[0] = max(l[0], lh + rh + root.data)
				return root.data + max(lh, rh)
			if root.left != None:
				return root.data + lh
			else:
				return root.data + rh
		y = fun(root)
		if root.left != None and root.right != None:
			return l[0]
		return max(y, l[0])


import sys

class Solution:
	maximum = -1000000

	def dfs(self, root, rt):
		if not root:
			return -1000000
		l = self.dfs(root.left, rt)
		r = self.dfs(root.right, rt)
		if root == rt:
			l = 0 if l == -1000000 else l
			r = 0 if r == -1000000 else r
			self.maximum = max(self.maximum, l + root.data + r)
		elif root.left and root.right:
			self.maximum = max(self.maximum, l + root.data + r)
		return root.data + (0 if max(l, r) == -1000000 else max(l, r))

	def maxPathSum(self, root):
		self.dfs(root, root)
		return self.maximum


class Solution:

	def maxPathSumUtil(self, root, res):
		if root is None:
			return 0
		if not root.left and (not root.right):
			return root.data
		ls = self.maxPathSumUtil(root.left, res)
		rs = self.maxPathSumUtil(root.right, res)
		if root.left is not None and root.right is not None:
			res[0] = max(res[0], ls + rs + root.data)
			return max(ls, rs) + root.data
		if root.left is None:
			return rs + root.data
		else:
			return ls + root.data

	def maxPathSum(self, root):
		res = [float('-inf')]
		res1 = self.maxPathSumUtil(root, res)
		if root.left and root.right:
			return res[0]
		return max(res[0], res1)


class Solution:
	ans = 0

	def solve(self, root, parent):
		if root == None:
			return 0
		if root.left != None and root.right != None:
			l = self.solve(root.left, root)
			r = self.solve(root.right, root)
			self.ans = max(self.ans, l + r + root.data)
			return root.data + max(l, r)
		elif root.left != None:
			l = self.solve(root.left, root)
			if parent == None:
				self.ans = max(self.ans, l + root.data)
			return root.data + l
		elif root.right != None:
			r = self.solve(root.right, root)
			if parent == None:
				self.ans = max(self.ans, r + root.data)
			return root.data + r
		else:
			return root.data

	def maxPathSum(self, root):
		self.ans = -sys.maxsize
		self.solve(root, None)
		return self.ans


class Solution:

	def maxPathSum(self, root):
		self.res = -int(1000000000.0)

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


class Solution:

	def __init__(self):
		self.maxsum = -2 ** 63

	def MaxPathSum(self, root):
		if root == None:
			return 0
		if root.left == None and root.right == None:
			return root.data
		left = self.MaxPathSum(root.left)
		right = self.MaxPathSum(root.right)
		if root.left != None and root.right != None:
			self.maxsum = max(self.maxsum, left + right + root.data)
			return max(left, right) + root.data
		if root.left != None:
			return root.data + left
		else:
			return root.data + right

	def maxPathSum(self, root):
		INT_MIN = -2 ** 63
		self.maxsum = INT_MIN
		val = self.MaxPathSum(root)
		if root.left == None or root.right == None:
			self.maxsum = max(self.maxsum, val)
		return self.maxsum


class Solution:

	def maxPath(self, root, maxi):
		if root == None:
			return 0
		else:
			l = self.maxPath(root.left, maxi)
			r = self.maxPath(root.right, maxi)
			if l + r + root.data > maxi[0] and root.left != None and (root.right != None):
				maxi[0] = l + r + root.data
			if root.left == None and root.right != None:
				return r + root.data
			elif root.right == None and root.left != None:
				return l + root.data
			return max(l + root.data, r + root.data)

	def maxPathSum(self, root):
		maxi = [-10000000000000]
		r = self.maxPath(root, maxi)
		if root.left == None or root.right == None:
			return max(maxi[0], r)
		return maxi[0]


import math

class Solution:

	def maxPathSum(self, root):
		x = self._maxspecial(root, root)
		if x[0] == -math.inf:
			return x[1]
		elif (root.right == None or root.left == None) and x[0] < x[1]:
			return x[1]
		return x[0]

	def _maxspecial(self, node, root):
		if not node:
			return [-math.inf, -math.inf]
		if not node.right and (not node.left):
			return [-math.inf, node.data]
		(l, r) = (self._maxspecial(node.left, root), self._maxspecial(node.right, root))
		return [max(l[0], r[0], l[1] + r[1] + node.data), node.data + max(l[1], r[1])]


class Solution:

	def maxPathSum(self, root):

		def maxpath(node):
			if node == None:
				return 0
			if node.left == None and node.right == None:
				return node.data
			l = maxpath(node.left)
			r = maxpath(node.right)
			if node.left and node.right:
				maxi[0] = max(maxi[0], l + r + node.data)
				return max(l, r) + node.data
			if node.left == None:
				return r + node.data
			else:
				return l + node.data
		maxi = [-2 ** 32]
		maxy = maxpath(root)
		if root.left and root.right:
			return maxi[0]
		return max(maxi[0], maxy)


class Solution:

	def maxPathSum(self, root):
		maxValue = -99999999

		def func(root):
			nonlocal maxValue
			if root == None:
				return 0
			if root.left == None and root.right == None:
				return root.data
			leftsum = func(root.left)
			rightsum = func(root.right)
			if root.left and root.right:
				maxValue = max(maxValue, root.data + leftsum + rightsum)
				return max(leftsum, rightsum) + root.data
			else:
				if root.left:
					return root.data + leftsum
				if root.right:
					return root.data + rightsum
		res = func(root)
		if root.left and root.right:
			return maxValue
		return max(maxValue, res)


import math

class Solution:

	def maxPathSum(self, root):

		def iterate(root):
			if not root:
				return (0, -math.inf)
			sum_left = iterate(root.left)
			sum_right = iterate(root.right)
			left_sum = sum_left[0] + root.data if root.left else -math.inf
			right_sum = sum_right[0] + root.data if root.right else -math.inf
			max_sum_branch = 0
			if root.left or root.right:
				max_sum_branch = max(left_sum, right_sum)
			else:
				max_sum_branch = root.data
			if root.left and root.right:
				triangle_sum = (sum_left[0] if root.left else 0) + (sum_right[0] if root.right else 0) + root.data
			else:
				triangle_sum = -math.inf
			current_running_max_sum = max(sum_left[1], sum_right[1], triangle_sum)
			return (max_sum_branch, current_running_max_sum)
		left = iterate(root.left)
		right = iterate(root.right)
		max_sum = max(left[0] + root.data + right[0], left[1], right[1])
		return max_sum


class Solution:

	def maxPathSum(self, root):
		self.ans = -10 ** 9
		self.li = []

		def func(root, top):
			if root is None:
				return -10 ** 9
			if root.left is None and root.right is None:
				return root.data
			left = func(root.left, top)
			right = func(root.right, top)
			if root.left and root.right:
				self.ans = max(self.ans, left + right + root.data)
			return root.data + max(left, right)
		kk = func(root, root)
		if root.left is None or root.right is None:
			return max(kk, self.ans)
		return self.ans


def util(root):
	if root.left == None and root.right == None:
		return {'summ': float('-inf'), 'pathSumm': root.data}
	elif root.left == None and root.right:
		right = util(root.right)
		return {'summ': right['summ'], 'pathSumm': right['pathSumm'] + root.data}
	elif root.left and root.right == None:
		left = util(root.left)
		return {'summ': left['summ'], 'pathSumm': left['pathSumm'] + root.data}
	else:
		left = util(root.left)
		right = util(root.right)
		summ = max(left['summ'], right['summ'], left['pathSumm'] + right['pathSumm'] + root.data)
		pathSumm = max(left['pathSumm'], right['pathSumm']) + root.data
		return {'summ': summ, 'pathSumm': pathSumm}

class Solution:

	def maxPathSum(self, root):
		if root.left == None:
			right = util(root.right)
			return max(right['summ'], right['pathSumm'] + root.data)
		if root.right == None:
			left = util(root.left)
			return max(left['summ'], left['pathSumm'] + root.data)
		return util(root)['summ']


class Solution:

	def maxPathSum(self, root):
		ans = [-2 ** 32] * 1

		def fun(root):
			if root == None:
				return -2 ** 32
			if root.left == None and root.right == None:
				return root.data
			l = fun(root.left)
			r = fun(root.right)
			if l != None and r != None:
				ans[0] = max(ans[0], l + r + root.data)
			return max(l, r) + root.data
		x = fun(root)
		if root.left == None or root.right == None:
			return max(x, ans[0])
		return ans[0]


class Solution:

	def maxPathSum(self, root):
		self.maX = None
		root_sum = self.diveDeep(root)
		if not root.left or not root.right:
			if self.maX is None or root_sum > self.maX:
				return root_sum
		return self.maX

	def diveDeep(self, node):
		left = 0
		right = 0
		lT = False
		rT = False
		if node.left is not None:
			left = self.diveDeep(node.left)
			lT = True
		if node.right is not None:
			right = self.diveDeep(node.right)
			rT = True
		if lT:
			if rT:
				summ = left + right + node.data
				if self.maX is None or summ > self.maX:
					self.maX = summ
				return node.data + max(left, right)
			return node.data + left
		if rT:
			return node.data + right
		return node.data


class Solution:

	def maxPathSum(self, root):
		Sum = 0
		Max = float('-inf')

		def inOrder(node, Sum):
			nonlocal Max
			maxLeft = float('-inf')
			maxRight = float('-inf')
			if node.left:
				maxLeft = inOrder(node.left, Sum)
			if node.right:
				maxRight = inOrder(node.right, Sum)
			if not node.left and (not node.right):
				return node.data
			if node.left and node.right:
				localMax = maxLeft + maxRight + node.data
				if localMax > Max:
					Max = localMax
			return max(maxLeft, maxRight) + node.data
		if not root.left:
			root.left = Node(0)
		if not root.right:
			root.right = Node(0)
		inOrder(root, Sum)
		return Max


import sys

class Solution:

	def maxPathSum(self, root):

		def maxPath(root, maxi):
			if root == None:
				return 0
			left = maxPath(root.left, maxi)
			right = maxPath(root.right, maxi)
			if root.left == None:
				return right + root.data
			if root.right == None:
				return left + root.data
			maxi[0] = max(maxi[0], left + right + root.data)
			return root.data + max(left, right)
		maxi = [0] * 1
		maxi[0] = -sys.maxsize - 1
		res = maxPath(root, maxi)
		if root.left == None or root.right == None:
			return max(maxi[0], res)
		return maxi[0]


class Solution:

	def maxPathSum(self, root):

		def dfs(root):
			if root == None:
				return (-1e+100, -1e+100)
			if root.left == None and root.right == None:
				return (-1e+100, root.data)
			(best1, s1) = dfs(root.left)
			(best2, s2) = dfs(root.right)
			best = max(best1, best2)
			v = root.data
			p1 = max(s1, s2) + v
			return (max(best, s1 + s2 + v), p1)
		(a, b) = dfs(root)
		if root.left == None or root.right == None:
			return max(a, b)
		return a


INT_MIN = -2 ** 32

class Solution:

	def maxPathSumUtil(self, root, res):
		if root is None:
			return 0
		if not root.left and (not root.right):
			return root.data
		ls = self.maxPathSumUtil(root.left, res)
		rs = self.maxPathSumUtil(root.right, res)
		if root.left is not None and root.right is not None:
			res[0] = max(res[0], ls + rs + root.data)
			return max(ls, rs) + root.data
		if root.left is None:
			return rs + root.data
		else:
			return ls + root.data

	def maxPathSum(self, root):
		res = [INT_MIN]
		res1 = self.maxPathSumUtil(root, res)
		if root.left and root.right:
			return res[0]
		return max(res[0], res1)