Given a Binary Tree, find the maximum sum path from a leaf to root.
Example 1:
Input:
        1
       / \
      2   3 
Output:
4
Explanation: 
Following the path 3 -> 1, results in a
sum of 4, which is the maximum path sum
from leaf to root for the given tree.
Example 2:
Input:
       10
      /  \
    -2    7
    / \   
   8  -4    
Output:
17
Explanation : 
Following the path 7 -> 10, results in a
sum of 17, which is the maximum path sum
from leaf to root for the given tree.
Your task :
You don't need to read input or print anything. Your task is to complete the function maxPathSum() which takes the root node of the tree as input and returns an integer denoting the maximum possible leaf to root path sum.
Expected Time Complexity: O(n) , where n = number of nodes
Expected Auxiliary Space: O(1)
Constraints : 
1 <= Number of nodes <= 10^5
-10^{6} <= max sum path <= 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Range queries

Starter code: #User function Template for python3



class Solution:

    def maxPathSum(self, root):

        #code here

Solutions:
import sys

class Solution:

	def maxPathSum(self, root):
		if root == None:
			return -sys.maxsize
		if root.left == None and root.right == None:
			return root.data
		l = self.maxPathSum(root.left)
		r = self.maxPathSum(root.right)
		return root.data + max(l, r)


class Solution:

	def maxPathSum(self, root):

		def answer(root):
			if root == None:
				return float('-inf')
			if root.left == None and root.right == None:
				return root.data
			l = answer(root.left)
			r = answer(root.right)
			return max(l + root.data, r + root.data)
		return answer(root)


class Solution:

	def __init__(self):
		self.max_sum = -float('inf')
		self.target_node = None

	def _get_target_leaf(self, node, current_sum):
		if not node:
			return
		current_sum += node.data
		if not node.left and (not node.right):
			if current_sum > self.max_sum:
				self.max_sum = current_sum
				self.target_node = node
			return
		self._get_target_leaf(node.left, current_sum)
		self._get_target_leaf(node.right, current_sum)

	def maxPathSum(self, root):
		if not root:
			return 0
		self._get_target_leaf(root, 0)
		return self.max_sum


class Solution:

	def maxPathSum(self, root):
		ans = -1000000000.0

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


class Solution:

	def maxPathSum(self, root):
		ans = []
		if root is None:
			return 0

		def solve(root, x, ans):
			if root.left is None and root.right is None:
				x = x + root.data
				ans.append(x)
			else:
				if root.right:
					solve(root.right, x + root.data, ans)
				if root.left:
					solve(root.left, x + root.data, ans)
		solve(root, 0, ans)
		return max(ans)


class Solution:

	def solve(self, root, ans):
		if root == None:
			return
		ans.append(root.data)
		if root.left == None and root.right == None:
			k = sum(ans)
			self.ans = max(self.ans, k)
		self.solve(root.left, ans)
		self.solve(root.right, ans)
		ans.pop()

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


class Solution:

	def maxPathSum(self, root):
		if root is None:
			return 0
		if root.left is None and root.right is None:
			return root.data
		leftSumTree = self.maxPathSum(root.left)
		rightSumTree = self.maxPathSum(root.right)
		if leftSumTree == 0:
			return root.data + rightSumTree
		elif rightSumTree == 0:
			return root.data + leftSumTree
		else:
			return root.data + max(leftSumTree, rightSumTree)


class Solution:

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

		def rec(root, sum):
			nonlocal res
			if root.left == None and root.right == None:
				res = max(res, sum[0] + root.data)
				return
			if root.left:
				rec(root.left, [sum[0] + root.data])
			if root.right:
				rec(root.right, [sum[0] + root.data])
		rec(root, [0])
		return res


class Solution:

	def maxPathSum(self, root):

		def find(root, sm=0):
			if not root:
				return float('-inf')
			if not root.left and (not root.right):
				return root.data
			return root.data + max(find(root.left), find(root.right))
		return find(root)


class Solution:

	def maxPathSum(self, root):
		if root == None:
			return 0
		if not root.left and (not root.right):
			return root.data
		if not root.left:
			return root.data + self.maxPathSum(root.right)
		if not root.right:
			return root.data + self.maxPathSum(root.left)
		return root.data + max(self.maxPathSum(root.left), self.maxPathSum(root.right))


class Solution:

	def maxPathSum(self, root):
		if root is None:
			return float('-inf')
		if root.left is None and root.right is None:
			return root.data
		return root.data + max(self.maxPathSum(root.left), self.maxPathSum(root.right))


class Solution:

	def maxPathSum(self, root):

		def helper(root):
			if not root:
				return -float('inf')
			if not root.left and (not root.right):
				return root.data
			l = root.data + helper(root.left)
			r = root.data + helper(root.right)
			return max(l, r)
		return helper(root)


class Solution:

	def maxPathSum(self, root):

		def fun(root, s):
			if root.left == None and root.right == None:
				maxi[0] = max(maxi[0], s + root.data)
				return
			if root.left:
				fun(root.left, s + root.data)
			if root.right:
				fun(root.right, s + root.data)
		maxi = [-2 ** 32]
		fun(root, 0)
		return maxi[0]


class Solution:

	def maxPathSum(self, root):
		if root == None:
			return 0
		ans = -10 ** 9
		notLeaf = False
		if root.left:
			notLeaf = True
			ans = max(ans, self.maxPathSum(root.left))
		if root.right:
			notLeaf = True
			ans = max(ans, self.maxPathSum(root.right))
		return root.data + ans * notLeaf


class Solution:

	def maxPathSum(self, root):
		import sys

		def rec(root):
			if root is None:
				return -sys.maxsize
			if root.left is None and root.right is None:
				return root.data
			return root.data + max(rec(root.left), rec(root.right))
		return rec(root)


class Solution:

	def maxPathSum(self, root):

		def find(root, sm):
			if root:
				if not root.left and (not root.right):
					ans[0] = max(ans[0], sm + root.data)
				sm += root.data
				find(root.left, sm)
				find(root.right, sm)
				sm -= root.data
			return
		ans = [-100000000]
		find(root, 0)
		return ans[0]


class Solution:

	def maxPathSum(self, root):

		def root_node(root):
			nonlocal sum1, maximum
			if root == None:
				return None
			sum1 += root.data
			if root.left == None and root.right == None and (sum1 > maximum):
				maximum = sum1
			if root_node(root.left) or root_node(root.right):
				return True
			sum1 -= root.data
			return False
		(sum1, maximum) = (0, -9999)
		root_node(root)
		return maximum


class Solution:

	def maxPathSum(self, root):
		(cr, m) = (0, float('-inf'))

		def maximal(r, cr):
			nonlocal m
			if not r:
				return 0
			cr += r.data
			if not r.left and (not r.right):
				m = max(m, cr)
			maximal(r.left, cr)
			maximal(r.right, cr)
		maximal(root, cr)
		return m


class Solution:

	def maxPathSum(self, root):
		return self.mS(root)

	def mS(self, root):
		if root == None:
			return -32676
		if root.left == None and root.right == None:
			return root.data
		l = self.mS(root.left)
		r = self.mS(root.right)
		return root.data + max(l, r)


class Solution:

	def maxPathSum(self, root):
		import sys

		def cal(root):
			if root == None:
				return -sys.maxsize
			if root.left == root.right == None:
				return root.data
			ls = cal(root.left)
			rs = cal(root.right)
			return max(ls, rs) + root.data
		return cal(root)


class Solution:

	def Postorder(self, root):
		if root == None:
			return -2 ** 63
		l = self.Postorder(root.left)
		r = self.Postorder(root.right)
		if root.left == None and root.right == None:
			return root.data
		return max(l, r) + root.data

	def maxPathSum(self, root):
		ans = self.Postorder(root)
		return ans


class Solution:

	def maxPathSum(self, root):

		def f(root):
			if not root:
				return 0
			left = f(root.left)
			right = f(root.right)
			new_left = max(0, left)
			new_right = max(0, right)
			if new_left == 0 and new_right == 0:
				if root.left and root.right:
					return max(left, right) + root.data
				elif root.left and (not root.right):
					return left + root.data
				elif not root.left and root.right:
					return right + root.data
				elif not root.left and (not root.right):
					return root.data
			return max(new_left, new_right) + root.data
		return f(root)


class Solution:

	def maxPathSum(self, root):

		def dfs(root, sm):
			if not root:
				return 0
			sm = sm + root.data
			if not root.left and (not root.right):
				return sm
			if not root.left:
				return dfs(root.right, sm)
			if not root.right:
				return dfs(root.left, sm)
			return max(dfs(root.left, sm), dfs(root.right, sm))
		return dfs(root, 0)


class Solution:

	def maxPathSum(self, root):
		if root is None:
			return
		l = self.maxPathSum(root.left)
		r = self.maxPathSum(root.right)
		if l is None and r is None:
			return root.data
		if l is None:
			return r + root.data
		if r is None:
			return l + root.data
		return max(l, r) + root.data


class Solution:

	def maxPathSum(self, root):
		if root == None:
			return -999999999
		if root.left == None and root.right == None:
			return root.data
		left = self.maxPathSum(root.left)
		right = self.maxPathSum(root.right)
		sum = max(left, right) + root.data
		return sum


class Solution:

	def pathToTarget(self, root, target, q):
		if root is None:
			return False
		self.sm += root.data
		if root.left is None and root.right is None and (self.sm > self.maxsum):
			self.maxsum = self.sm
		if self.pathToTarget(root.left, target, q) or self.pathToTarget(root.right, target, q):
			q.append(root.data)
			return True
		self.sm -= root.data
		return False

	def postorder(self, root, q):
		if root is None:
			return
		self.sm += root.data
		if root.left is None and root.right is None:
			if self.sm > self.maxsum:
				self.maxsum = self.sm
				q.append(root)
				self.target = root
		self.postorder(root.left, q)
		self.postorder(root.right, q)

	def maxPathSum(self, root):
		q = []
		self.target = None
		self.rootd = root
		self.maxsum = -9999
		self.sm = 0
		q = []
		self.pathToTarget(root, self.target, q)
		return self.maxsum


class Solution:

	def maxPathSum(self, root):
		if root is None:
			return 0
		if root.left is None:
			return root.data + self.maxPathSum(root.right)
		if root.right is None:
			return root.data + self.maxPathSum(root.left)
		return root.data + max(self.maxPathSum(root.left), self.maxPathSum(root.right))


class Solution:

	def util(self, root):
		if not root:
			return -10 ** 7
		ls = self.util(root.left)
		rs = self.util(root.right)
		mx = max(ls, rs)
		if mx == -10 ** 7:
			mx = 0
		return root.data + mx

	def maxPathSum(self, root):
		return self.util(root)


class Solution:

	def maxPathSum(self, root):
		if root == None:
			return float('-inf')
		if root.left == None and root.right == None:
			return root.data
		maxleft = self.maxPathSum(root.left)
		maxright = self.maxPathSum(root.right)
		return root.data + max(maxleft, maxright)


class Solution:

	def maxPathSum(self, root):
		if not root:
			return -float('inf')
		if not root.left and (not root.right):
			return root.data
		lft = self.maxPathSum(root.left)
		rght = self.maxPathSum(root.right)
		return max(lft, rght) + root.data


class Solution:

	def maxPathSum(self, root):

		def solve(root, dic, lis):
			if root == None:
				return None
			lis.append(root.data)
			if root.left == None and root.right == None:
				dic.append(sum(lis))
			solve(root.left, dic, lis)
			solve(root.right, dic, lis)
			lis.pop()
			return dic
		lis = solve(root, [], [])
		res = -100000000
		return max(lis)
		for i in lis:
			res = max(res, sum(i))
		return res


class Solution:

	def maxPathSum(self, root):

		def dfs(root):
			nonlocal sum1, maximum
			if not root:
				return None
			sum1 += root.data
			if root.left is None and root.right is None and (sum1 > maximum):
				maximum = sum1
			if dfs(root.left) or dfs(root.right):
				return True
			sum1 -= root.data
			return False
		(sum1, maximum) = (0, -99999)
		dfs(root)
		return maximum


class Solution:

	def maxPathSum(self, root):
		temp = root
		val = []
		s = 0

		def ino(temp, s):
			if temp == None:
				return
			if temp.left == None and temp.right == None:
				s += temp.data
				val.append(s)
				return
			s += temp.data
			l = ino(temp.left, s)
			r = ino(temp.right, s)
		ino(temp, s)
		maxi = max(val)
		return maxi


class Solution:

	def maxPathSum(self, root):

		def traverse(temp, l, s):
			if temp == None:
				return
			if temp.left is None and temp.right is None:
				s += temp.data
				l.append(s)
				return
			s += temp.data
			traverse(temp.left, l, s)
			traverse(temp.right, l, s)
		l = []
		temp = root
		s = 0
		traverse(temp, l, s)
		return max(l)


class Solution:

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

		def helper(root, s):
			nonlocal max_path
			if not root:
				return 0
			s += root.data
			if not root.left and (not root.right):
				max_path = max(max_path, s)
				return
			helper(root.left, s)
			helper(root.right, s)
		helper(root, 0)
		return max_path


class Solution:

	def maxPathSum(self, root):

		def fun(root):
			if root == None:
				return -10000000
			if root.left == None and root.right == None:
				return root.data
			l = fun(root.left)
			r = fun(root.right)
			return max(l, r) + root.data
		return fun(root)


class Solution:

	def maxPathSum(self, root):

		def solve(root):
			if root is None:
				return 0
			left = solve(root.left)
			right = solve(root.right)
			if left == 0:
				return root.data + right
			elif right == 0:
				return root.data + left
			else:
				return root.data + max(left, right)
		ans = solve(root)
		return ans


class Solution:

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

	def check(self, a, s):
		if a == None:
			return
		s += a.data
		if a.left == None and a.right == None:
			self.c = max(self.c, s)
		self.check(a.left, s)
		self.check(a.right, s)

	def maxPathSum(self, root):
		self.check(root, 0)
		return self.c


class Solution:

	def maxPathSum(self, root):
		if root.left != None and root.right == None:
			return root.data + self.maxPathSum(root.left)
		if root.left == None and root.right != None:
			return root.data + self.maxPathSum(root.right)
		if root.left == root.right == None:
			return root.data
		w1 = self.maxPathSum(root.left)
		w2 = self.maxPathSum(root.right)
		return root.data + max(w1, w2)


import math

class Solution:

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

def dfs(n):
	if not n:
		return -math.inf
	if n.left is None and n.right is None:
		return n.data
	l = dfs(n.left)
	r = dfs(n.right)
	return max(l, r) + n.data


import math

class Solution:

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

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


from collections import deque

class Solution:

	def maxPathSum(self, root):
		if root.left == None and root.right == None:
			return root.data
		l = -float('inf')
		r = -float('inf')
		if root.left:
			l = self.maxPathSum(root.left)
		if root.right:
			r = self.maxPathSum(root.right)
		return max(l, r) + root.data


class Solution:

	def maxPathSum(self, root):

		def dfs(root):
			if not root:
				return float('-inf')
			if not root.left and (not root.right):
				return root.data
			return root.data + max(dfs(root.left), dfs(root.right))
		return dfs(root)


import sys

class Solution:

	def find(self, root):
		if not root:
			return -sys.maxsize - 1
		if not root.left and (not root.right):
			return root.data
		left = self.find(root.left)
		right = self.find(root.right)
		return left + root.data if left > right else right + root.data

	def maxPathSum(self, root):
		if not root:
			return 0
		return self.find(root)


class Solution:
	res = -(10 ** 6 + 1)

	def maxPathSum(self, root):
		self.maxPathSumUtil(0, root)
		return self.res

	def maxPathSumUtil(self, curSum, root):
		if root == None:
			return
		curSum += root.data
		if root.left == None and root.right == None:
			if curSum > self.res:
				self.res = curSum
			return
		self.maxPathSumUtil(curSum, root.left)
		self.maxPathSumUtil(curSum, root.right)


class Solution:
	msum = -(10 ** 6 + 1)
	target = None
	l = []

	def solve(self, root, csum):
		if root == None:
			return
		csum += root.data
		if root.left == None and root.right == None:
			if csum > self.msum:
				self.msum = csum
				self.target = root
		self.solve(root.left, csum)
		self.solve(root.right, csum)

	def maxPathSum(self, root):
		self.solve(root, 0)
		return self.msum


class Solution:

	def maxPathSum(self, root):
		if root.left is None and root.right is None:
			return root.data
		elif root.left is not None and root.right is None:
			return root.data + self.maxPathSum(root.left)
		elif root.left is None and root.right is not None:
			return root.data + self.maxPathSum(root.right)
		else:
			return max(root.data + self.maxPathSum(root.left), root.data + self.maxPathSum(root.right))


class Solution:

	def maxPathSum(self, root):
		if not root:
			return 0

		def helper(root):
			if not root:
				return 0
			if not root.left:
				value = helper(root.right)
			elif not root.right:
				value = helper(root.left)
			else:
				value = max(helper(root.left), helper(root.right))
			return value + root.data
		return helper(root)


class Solution:

	def maxPathSum(self, root):
		if not root:
			return -1
		sum = root.data
		myList = []

		def helper(root, sum):
			if not root:
				return 0
			if not root.left and (not root.right):
				if len(myList) == 0:
					myList.append(sum)
				elif myList[0] < sum:
					myList[0] = sum
			if root.left:
				helper(root.left, sum + root.left.data)
			if root.right:
				helper(root.right, sum + root.right.data)
			return myList
		return helper(root, sum)[0]


class Solution:

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


import sys

class Solution:

	def dfs(self, root, msum):
		if root is None:
			return msum
		if root.right is None and root.left is None:
			return root.data
		lsum = self.dfs(root.left, msum) + root.data
		rsum = self.dfs(root.right, msum) + root.data
		msum = max(lsum, rsum, msum)
		return msum

	def maxPathSum(self, root):
		return self.dfs(root, -sys.maxsize - 1)


class Solution:

	def __init__(self):
		self.l = []
		self.ans = -10 ** 9 + 9

	def maxPathSum(self, root):

		def helper(root):
			if root is None:
				return
			self.l.append(root.data)
			if root.left is None and root.right is None:
				su = 0
				for i in self.l:
					su += i
				self.ans = max(self.ans, su)
			helper(root.left)
			helper(root.right)
			self.l.pop()
		helper(root)
		return self.ans


import math

class Solution:

	def maxPathSum(self, root):
		self.max_sum = -math.inf

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


class Solution:

	def helper(self, node, sum1):
		if node is None:
			return
		if not node.left and (not node.right):
			self.max1 = max(self.max1, sum1 + node.data)
		self.helper(node.left, sum1 + node.data)
		self.helper(node.right, sum1 + node.data)

	def maxPathSum(self, root):
		self.max1 = float('-inf')
		self.helper(root, 0)
		return self.max1


import math

class Solution:

	def maxPathSum(self, root):
		if root == None:
			return -math.inf
		if root.left == None and root.right == None:
			return root.data
		left = root.data + self.maxPathSum(root.left)
		right = root.data + self.maxPathSum(root.right)
		return max(left, right)


class Solution:

	def __init__(self):
		self.summ = []

	def trav(self, root, s):
		if root.left == None and root.right == None:
			self.summ.append(s + root.data)
			return
		if root.left != None:
			self.trav(root.left, s + root.data)
		if root.right != None:
			self.trav(root.right, s + root.data)

	def maxPathSum(self, root):
		self.trav(root, 0)
		return max(self.summ)


INT_MIN = -(1 << 63)

class Solution:

	def maxPathSum(self, root):
		if root is None:
			return INT_MIN
		if root.left is None and root.right is None:
			return root.data
		ls = self.maxPathSum(root.left)
		rs = self.maxPathSum(root.right)
		return root.data + max(ls, rs)


class Solution:

	def maxPathSum(self, root):
		if not root:
			return 0
		else:
			p = root.data
			if root.left and root.right:
				return p + max(self.maxPathSum(root.left), self.maxPathSum(root.right))
			elif root.left:
				return p + self.maxPathSum(root.left)
			elif root.right:
				return p + self.maxPathSum(root.right)
			else:
				return p


class Solution:

	def maxPathSum(self, root):
		return self.path_sum(root, 0)

	def path_sum(self, node, total):
		total += node.data
		if node.left == None and node.right == None:
			return total
		if node.left == None and node.right != None:
			return self.path_sum(node.right, total)
		if node.right == None and node.left != None:
			return self.path_sum(node.left, total)
		return max(self.path_sum(node.right, total), self.path_sum(node.left, total))


class Solution:

	def maxPathSum(self, root):

		def find_max(node):
			if not node:
				return None
			if node:
				right_max = find_max(node.right)
				left_max = find_max(node.left)
				if right_max and left_max:
					max_node = max(right_max, left_max) + node.data
				elif right_max and (not left_max):
					max_node = right_max + node.data
				elif not right_max and left_max:
					max_node = left_max + node.data
				elif not right_max and (not left_max):
					max_node = node.data
				return max_node
		max_value = find_max(root)
		return max_value


class Solution:

	def getPaths(self, root, temp, result):
		if root:
			temp.append(root.data)
			self.getPaths(root.left, temp, result)
			self.getPaths(root.right, temp, result)
			if root.left == None and root.right == None:
				temp_ = sum(temp)
				result.append(temp_)
			temp.pop()

	def maxPathSum(self, root):
		temp = []
		result = []
		self.getPaths(root, temp, result)
		return max(result)


class Solution:

	def maxPathSum(self, root):
		summ = [0]

		def sumpath(root, summ):
			ls = -99999
			rs = -99999
			if not root.left and (not root.right):
				summ[0] = root.data
				return summ[0]
			if root.left:
				ls = sumpath(root.left, summ)
			if root.right:
				rs = sumpath(root.right, summ)
			summ[0] = max(ls, rs) + root.data
			return summ[0]
		sumpath(root, summ)
		return summ[0]


class Solution:

	def maxPathSum(self, root):

		def helper(root):
			if not root:
				return -999999999
			if root.left == None and root.right == None:
				return root.data
			l = helper(root.left)
			r = helper(root.right)
			return root.data + max(l, r)
		a = helper(root)
		return a


import sys

class Solution:

	def maxPathSum(self, root):

		def psum(root, val):
			nonlocal maxp
			if root is None:
				return
			val += root.data
			if root.left is None and root.right is None:
				maxp = max(maxp, val)
			psum(root.left, val) or psum(root.right, val)
		val = 0
		maxp = -sys.maxsize
		psum(root, val)
		return maxp


class Solution:

	def maxPathSum(self, root):

		def rec(root, curr, max_):
			if not root:
				return max_
			curr += root.data
			if not root.right and (not root.left):
				max_ = max(curr, max_)
				return max_
			temp = max(rec(root.right, curr, max_), rec(root.left, curr, max_))
			return temp
		max_ = rec(root, 0, -100000000)
		return max_


class Solution:

	def maxPathSum(self, root):
		if not root:
			return 0

		def cursor(r, s):
			if not r:
				return None
			s += r.data
			if r.left == None and r.right == None:
				return s
			left = cursor(r.left, s)
			right = cursor(r.right, s)
			if left != None and right != None:
				return max(left, right)
			return left if left else right
		return cursor(root, 0)


class Solution:

	def maxPathSum(self, root):
		self.maxi = -9868695968
		self.helper(root, sum=0)
		return self.maxi

	def helper(self, root, sum):
		if root == None:
			return -1
		sum += root.data
		left = self.helper(root.left, sum)
		right = self.helper(root.right, sum)
		if root.left == None and root.right == None:
			self.maxi = max(self.maxi, sum)
		return max(left, right)


import sys

class Solution:

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

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


class Solution:

	def maxPathSum(self, root):

		def dfs(root):
			if not root:
				return -1000
			else:
				l = dfs(root.left)
				r = dfs(root.right)
				if l == -1000 and r == -1000:
					return root.data
				else:
					return max(l, r) + root.data
		return dfs(root)


class Solution:

	def maxPathSum(self, root):

		def trav(summ, root):
			if not root:
				return 0
			summ += root.data
			if not root.left and (not root.right):
				self.maxx = max(self.maxx, summ)
			trav(summ, root.left)
			trav(summ, root.right)
			summ -= root.data
		self.maxx = float('-inf')
		trav(0, root)
		return self.maxx


from math import inf

class Solution:

	def maxPathSum(self, root):
		self.maxi = -inf

		def dfs(root, sums):
			if not root:
				return
			sums += root.data
			if not root.left and (not root.right):
				self.maxi = max(self.maxi, sums)
			dfs(root.left, sums)
			dfs(root.right, sums)
			sums -= root.data
		dfs(root, 0)
		return self.maxi


import math

class Solution:

	def maxPathSum(self, root):
		maxsum = -math.inf

		def dfs(root, cursum):
			nonlocal maxsum
			if root == None:
				return
			if root.left == None and root.right == None:
				cursum += root.data
				maxsum = max(maxsum, cursum)
			else:
				dfs(root.left, cursum + root.data)
				dfs(root.right, cursum + root.data)
		dfs(root, 0)
		return maxsum


class Solution:

	def maxPathSum(self, root):
		global maxsum
		maxsum = -999999

		def S(root, sum):
			global maxsum
			if not root:
				return 0
			if root.left == None and root.right == None and (sum + root.data > maxsum):
				maxsum = sum + root.data
			S(root.left, sum + root.data)
			S(root.right, sum + root.data)
		S(root, 0)
		return maxsum