# Maximum Sum in a Binary Tree

##### January 1, 2024

## Problem #

find the maximum sum of values in a binary tree where each node has a value and two children. The goal is to find the maximum sum of values that can be obtained by traveling upwards from a leaf to the root.

## Solution #

Here’s the Python code to design an efficient algorithm that finds the maximum sum of values from a leaf to the root in a binary tree:

```
class TreeNode:
def __init__(self, value=0, left=None, right=None):
self.value = value
self.left = left
self.right = right
def maxPathSum(root):
"""
Find the maximum sum from any leaf to the root in a binary tree.
Args:
root (TreeNode): The root node of the binary tree.
Returns:
int: The maximum sum from any leaf to the root.
"""
def maxSumToRoot(node):
if not node:
return 0
# Calculate the maximum sum from left and right child to the current node
left_sum = maxSumToRoot(node.left)
right_sum = maxSumToRoot(node.right)
# Return the maximum of the two sums, plus the current node's value
return max(left_sum, right_sum) + node.value
return maxSumToRoot(root)
# Example Usage
# Creating a binary tree:
# 10
# / \
# 2 10
# / \ \
# 20 1 -25
# / \
# 3 4
root = TreeNode(10)
root.left = TreeNode(2)
root.right = TreeNode(10)
root.left.left = TreeNode(20)
root.left.right = TreeNode(1)
root.right.right = TreeNode(-25)
root.right.right.left = TreeNode(3)
root.right.right.right = TreeNode(4)
# Calculate the maximum sum
max_sum = maxPathSum(root)
print(max_sum)
```

In this code:

`TreeNode`

class defines the structure of a node in the binary tree.`maxPathSum`

function computes the maximum sum from any leaf node to the root.- The
`maxSumToRoot`

function is a helper function used recursively to compute the maximum sum up to the current node from its children.

In the provided example, the maximum sum path is found by going from the leaf node with value `20`

to the root, resulting in a sum of `20 + 2 + 10 = 32`

.