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

Binary Trees

Contents

ProblemExamplesSolutionAlgorithmCode

Problem Statement❯

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.

Examples❯

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

Solution❯

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.

Algorithm Steps❯

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

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#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;
}

Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...