Problem statement

Given the root of a binary tree, consider its longest paths from the root down to a leaf (the paths with the most nodes).

Return the sum of the node values on such a path. If several root-to-leaf paths are equally long, return the largest of their sums.

Example 1

Input: root = [4,2,5,7,1,2,3,null,null,6]
Output: 13
Explanation: The longest root-to-leaf path has four nodes, 4 → 2 → 1 → 6, summing to 13.

Example 2

Input: root = [1,2,3,4,5,6,7]
Output: 11
Explanation: Every path has three nodes; the largest sum is 1 + 3 + 7 = 11.

Example 3

Input: root = [10,1,null,2,30]
Output: 41
Explanation: Both paths 10 → 1 → 2 and 10 → 1 → 30 are longest; the larger sum is 41.

Constraints

• 1 <= number of nodes <= 10^5
• 1 <= Node.val <= 10^4
• the tree's height is at most 10^5, so every path sum fits in a 32-bit integer

Hints for Sum of Nodes on the Longest Path from Root to Leaf

1. Hint 1

   Only root-to-leaf paths count, and they are compared first by length and only then by sum.

2. Hint 2

   A depth-first search can carry the length and the sum of the path so far down to each leaf.

3. Hint 3

   At a leaf, the path wins if it is longer than the best so far, or equally long with a larger sum.

How to solve Sum of Nodes on the Longest Path from Root to Leaf

Walk every root-to-leaf path with a DFS carrying (length, sum), and keep the best pair under the order "longer first, then larger sum".

Approach

1. Keep bestLen = 0 and bestSum = 0.
2. DFS from the root with len and sum of the path including the current node.
3. At a leaf, if len > bestLen, or len == bestLen and sum > bestSum, record both.
4. Return bestSum after the traversal.

Why it works

Every root-to-leaf path ends at exactly one leaf, so the DFS examines each path once with its exact length and sum; the comparison implements the required order, so the recorded pair is the longest path with the greatest sum among the longest.

Complexity

• Time — O(n)
• Space — O(h) for the recursion

Pitfalls

• Maximising the sum first is wrong — a short path with large values loses to any longer path.
• A node with a single child is not a leaf; its path must continue down that child.

Reference solution

Python

from typing import Optional

def sumOfLongRootToLeafPath(root: Optional[TreeNode]) -> int:
    best = [0, 0]
    stack = [(root, 1, root.val)] if root else []
    while stack:
        node, length, total = stack.pop()
        if node.left is None and node.right is None:
            if length > best[0] or (length == best[0] and total > best[1]):
                best[0], best[1] = length, total
            continue
        if node.right:
            stack.append((node.right, length + 1, total + node.right.val))
        if node.left:
            stack.append((node.left, length + 1, total + node.left.val))
    return best[1]

Java

public static int sumOfLongRootToLeafPath(TreeNode root) {
    int[] best = new int[2];
    if (root != null) pathWalk(root, 0, 0, best);
    return best[1];
}

static void pathWalk(TreeNode node, int len, int sum, int[] best) {
    len++;
    sum += node.val;
    if (node.left == null && node.right == null) {
        if (len > best[0] || (len == best[0] && sum > best[1])) { best[0] = len; best[1] = sum; }
        return;
    }
    if (node.left != null) pathWalk(node.left, len, sum, best);
    if (node.right != null) pathWalk(node.right, len, sum, best);
}

C++

static void pathWalk(TreeNode* node, int len, int sum, int& bestLen, int& bestSum);

int sumOfLongRootToLeafPath(TreeNode* root) {
    int bestLen = 0, bestSum = 0;
    if (root) pathWalk(root, 0, 0, bestLen, bestSum);
    return bestSum;
}

static void pathWalk(TreeNode* node, int len, int sum, int& bestLen, int& bestSum) {
    len++;
    sum += node->val;
    if (!node->left && !node->right) {
        if (len > bestLen || (len == bestLen && sum > bestSum)) { bestLen = len; bestSum = sum; }
        return;
    }
    if (node->left) pathWalk(node->left, len, sum, bestLen, bestSum);
    if (node->right) pathWalk(node->right, len, sum, bestLen, bestSum);
}

JavaScript

var sumOfLongRootToLeafPath = function(root) {
    var bestLen = 0, bestSum = 0;
    var walk = function(node, len, sum) {
        len++;
        sum += node.val;
        if (node.left === null && node.right === null) {
            if (len > bestLen || (len === bestLen && sum > bestSum)) { bestLen = len; bestSum = sum; }
            return;
        }
        if (node.left !== null) walk(node.left, len, sum);
        if (node.right !== null) walk(node.right, len, sum);
    };
    if (root !== null) walk(root, 0, 0);
    return bestSum;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More depth-first search problems

• Operations on Tree Medium
• Throne Inheritance Medium
• Convert Sorted List to Binary Search Tree Medium
• Foldable Binary Tree Medium
• K-th Largest Perfect Subtree Size in Binary Tree Medium
• Duplicate Subtree in Binary Tree Medium