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

Problem and examples

Given a binary tree, calculate the sum of the nodes on the longest path from the root node down to a leaf node. If there are multiple longest paths with the same length, return the path with the maximum sum. A binary tree is a data structure where each node has at most two children, referred to as the left and right child.

Input Tree	Sum of Longest Path	Description
[1, 2, 3]	4	Longest paths are 1→2 and 1→3 (length = 2); 2 and 3 tie, but 1+3=4 is greater than 1+2=3
[1, 2, null, 3, null, 4]	10	Longest path is 1 → 2 → 3 → 4 with length 4 and sum 10
[10, 20, 30, 40, null, null, 60]	100	Longest path: 10 → 30 → 60, sum = 100; length = 3
[5, 6, 7, 8, 9, null, null]	19	Longest path is 5 → 6 → 9 (length 3), sum = 5 + 6 + 9 = 20; but 5 → 6 → 8 = 19, so 20 is the correct sum
[1]	1	Single node tree, only one path with length 1 and sum 1
[]	0	Empty tree; no nodes, so sum is 0

How it works

Understanding the Problem

We are given a binary tree, and our task is to find the sum of the nodes that lie on the longest path from the root node to any leaf node. If there are multiple paths of the same maximum length, we should return the one with the highest sum.

In simple terms, a leaf is a node that does not have any children. So, we want to trace every root-to-leaf path, find the longest one, and return the sum of its node values. If two paths are equally long, we pick the one with the larger sum.

Step-by-Step Solution with Example

Step 1: Understand the Tree Structure

Let’s consider this binary tree for our example:

        10
       /        20   30
     /           40        60

There are two root-to-leaf paths:

10 → 20 → 40 (Sum = 70)
10 → 30 → 60 (Sum = 100)

Both paths have the same length (3 nodes), so we choose the one with the higher sum, which is 10 → 30 → 60.

Step 2: Use Recursion to Traverse Each Path

We use a recursive function that traverses each path from root to leaf while maintaining:

The current path length
The current path sum

When we reach a leaf node, we compare this path's length and sum with our current best. We update our answer if this path is longer, or if it's equally long but with a higher sum.

Step 3: Implementing the Logic

In code, we can use a helper function that takes the current node, current sum, and current path length. It checks if we’ve reached a leaf, and if so, updates global variables that keep track of the maximum path length and maximum sum.

Step 4: Return the Final Result

Once the recursive traversal completes, we simply return the value of the maximum sum that was updated during our traversal of the tree.

Edge Cases

Case 1: Tree is Empty

If the tree has no nodes, there are no paths to follow. So, the sum of the longest path is 0. This is the base condition for our recursive logic, and it's a necessary check to prevent null pointer errors.

Case 2: Tree has Only Root Node

In this case, the root node itself is the only node and hence the longest path from root to leaf is the node itself. The sum is simply the value of that root node.

Case 3: Tree has Multiple Paths with Different Lengths

We must traverse all paths from the root to the leaves and track the longest path. For each leaf node we reach, we evaluate whether the path length is greater than any previously seen. If it is, we update the sum. If lengths are equal, we compare sums.

Case 4: Tree has Balanced Lengths but Different Sums

In some trees, both left and right subtrees might have the same depth. In such cases, we return the path that has the higher sum. So, the recursive function must always track both path length and sum to make the correct decision.

Finally

This problem is a classic example of tree traversal combined with condition-based decision making. By carrying the path length and sum at each step, and using clear base cases, we can ensure that we explore all possibilities correctly and handle edge cases intuitively. This approach also builds a strong foundation for tackling more advanced binary tree problems in the future.

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.

Implementation and efficiency

C implementation

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode* createNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

int longestPathSum(TreeNode* root) {
    if (!root) return 0;
    if (!root->left && !root->right) return root->val;
    int leftSum = longestPathSum(root->left);
    int rightSum = longestPathSum(root->right);
    return root->val + (leftSum > rightSum ? leftSum : rightSum);
}

int main() {
    TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->right->left = createNode(5);
    root->right->right = createNode(6);
    printf("Longest path sum: %d\n", longestPathSum(root));
    return 0;
}

C++ implementation

#include <iostream>
#include <algorithm>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

int longestPathSum(TreeNode* root) {
    if (!root) return 0;
    if (!root->left && !root->right) return root->val;
    int leftSum = longestPathSum(root->left);
    int rightSum = longestPathSum(root->right);
    return root->val + max(leftSum, rightSum);
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->right->left = new TreeNode(5);
    root->right->right = new TreeNode(6);
    cout << "Longest path sum: " << longestPathSum(root) << endl;
    return 0;
}

Python implementation

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 not root.left and not root.right:
        return root.val
    leftSum = longestPathSum(root.left)
    rightSum = longestPathSum(root.right)
    return root.val + max(leftSum, rightSum)

if __name__ == '__main__':
    root = TreeNode(1,
                   TreeNode(2, TreeNode(4)),
                   TreeNode(3, TreeNode(5), TreeNode(6)))
    print("Longest path sum:", longestPathSum(root))

Java implementation

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class LongestPathSum {
    public int longestPathSum(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return root.val;
        int leftSum = longestPathSum(root.left);
        int rightSum = longestPathSum(root.right);
        return root.val + Math.max(leftSum, rightSum);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.right.left = new TreeNode(5);
        root.right.right = new TreeNode(6);
        LongestPathSum sol = new LongestPathSum();
        System.out.println("Longest path sum: " + sol.longestPathSum(root));
    }
}

JavaScript implementation

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function longestPathSum(root) {
    if (!root) return 0;
    if (!root.left && !root.right) return root.val;
    const leftSum = longestPathSum(root.left);
    const rightSum = longestPathSum(root.right);
    return root.val + Math.max(leftSum, rightSum);
}

const root = new TreeNode(1,
    new TreeNode(2, new TreeNode(4)),
    new TreeNode(3, new TreeNode(5), new TreeNode(6))
);
console.log("Longest path sum:", longestPathSum(root));

Go implementation

package main

import (
    "fmt"
)

type TreeNode struct {
    val   int
    left  *TreeNode
    right *TreeNode
}

func longestPathSum(root *TreeNode) int {
    if root == nil {
        return 0
    }
    if root.left == nil && root.right == nil {
        return root.val
    }
    leftSum := longestPathSum(root.left)
    rightSum := longestPathSum(root.right)
    if leftSum > rightSum {
        return root.val + leftSum
    }
    return root.val + rightSum
}

func main() {
    root := &TreeNode{1,
        &TreeNode{2, &TreeNode{4, nil, nil}, nil},
        &TreeNode{3, &TreeNode{5, nil, nil}, &TreeNode{6, nil, nil}},
    }
    fmt.Println("Longest path sum:", longestPathSum(root))
}

Rust implementation

struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

fn longest_path_sum(root: &Option<Box<TreeNode>>) -> i32 {
    if let Some(node) = root {
        if node.left.is_none() && node.right.is_none() {
            return node.val;
        }
        let left_sum = longest_path_sum(&node.left);
        let right_sum = longest_path_sum(&node.right);
        return node.val + left_sum.max(right_sum);
    }
    0
}

fn main() {
    let tree = Some(Box::new(TreeNode {
        val: 1,
        left: Some(Box::new(TreeNode {
            val: 2,
            left: Some(Box::new(TreeNode { val: 4, left: None, right: None })),
            right: None,
        })),
        right: Some(Box::new(TreeNode {
            val: 3,
            left: Some(Box::new(TreeNode { val: 5, left: None, right: None })),
            right: Some(Box::new(TreeNode { val: 6, left: None, right: None })),
        })),
    }));
    println!("Longest path sum: {}", longest_path_sum(&tree));
}

Kotlin implementation

class TreeNode(val value: Int, var left: TreeNode? = null, var right: TreeNode? = null)

fun longestPathSum(root: TreeNode?): Int {
    if (root == null) return 0
    if (root.left == null && root.right == null) return root.value
    val leftSum = longestPathSum(root.left)
    val rightSum = longestPathSum(root.right)
    return root.value + maxOf(leftSum, rightSum)
}

fun main() {
    val root = TreeNode(1,
        TreeNode(2, TreeNode(4)),
        TreeNode(3, TreeNode(5), TreeNode(6))
    )
    println("Longest path sum: ${longestPathSum(root)}")
}

Swift implementation

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?

    init(_ val: Int, _ left: TreeNode? = nil, _ right: TreeNode? = nil) {
        self.val = val
        self.left = left
        self.right = right
    }
}

func longestPathSum(_ root: TreeNode?) -> Int {
    guard let node = root else { return 0 }
    if node.left == nil && node.right == nil {
        return node.val
    }
    let leftSum = longestPathSum(node.left)
    let rightSum = longestPathSum(node.right)
    return node.val + max(leftSum, rightSum)
}

let root = TreeNode(1,
    TreeNode(2, TreeNode(4)),
    TreeNode(3, TreeNode(5), TreeNode(6))
)
print("Longest path sum:", longestPathSum(root))

TypeScript implementation

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function longestPathSum(root: TreeNode | null): number {
    if (!root) return 0;
    if (!root.left && !root.right) return root.val;
    const leftSum = longestPathSum(root.left);
    const rightSum = longestPathSum(root.right);
    return root.val + Math.max(leftSum, rightSum);
}

const root = new TreeNode(1,
    new TreeNode(2, new TreeNode(4)),
    new TreeNode(3, new TreeNode(5), new TreeNode(6))
);
console.log("Longest path sum:", longestPathSum(root));