Calculate the Sum of Nodes on the Longest Path from Root to Leaf in a Binary Tree

Algorithm Steps

If the tree is empty, return 0.
If the current node is a leaf (no left and right children), return its value.
Recursively calculate the longest path sum for the left subtree and the right subtree.
Select the maximum sum between the left and right subtree.
Add the current node's value to the maximum sum and return the result.

Calculate the Sum of Nodes on the Longest Path from Root to Leaf in a Binary Tree - Code Examples Code

Python

Java

JavaScript

C++

Kotlin

Swift

Php

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def longestPathSum(root):
    if not root:
        return 0
    # If leaf node, return its value
    if not root.left and not root.right:
        return root.val
    leftSum = longestPathSum(root.left)
    rightSum = longestPathSum(root.right)
    return root.val + max(leftSum, rightSum)

# Example usage:
if __name__ == '__main__':
    # Construct binary tree:
    #         1
    #        / \
    #       2   3
    #      /   / \
    #     4   5   6
    root = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3, TreeNode(5), TreeNode(6)))
    print("Longest path sum:", longestPathSum(root))