Maximum Sum in a Binary Tree

Maximum Sum in a Binary Tree

January 1, 2024
medium
DFS

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.