Sum of nodes on the longest path from root to leaf node

Last Updated : 19 May, 2025

Given a binary tree containing n nodes. The task is to find the sum of all nodes on the longest path from root to leaf node. If two or more paths compete for the longest path, then the path having the maximum sum of nodes is considered.

Examples: 

Input: root[] = [4, 2, 5, 1, 3]
Output: 13
Explanation:

22

The highlighted nodes (4, 2, 3) above are part of the longest root to leaf path having sum = (4 + 2 + 3) = 9

Input: root[] = [4, 2, 5, 7, 1, 2, 3, N, N, 6, N]
Output: 13
Explanation:
The highlighted nodes (4, 2, 1, 6) above are part of the longest root to leaf path having sum = (4 + 2 + 1 + 6) = 13

Try it on GfG Practice
redirect icon

Table of Content

[Better Approach] Using level order traversal - O(n) Time and O(n) Space

The idea is to initialize maxSum and maxLen to 0, use a queue for level order traversal starting with the root, and while the queue is not empty, dequeue nodes and update maxLen and maxSum for leaf nodes, and enqueue their children with updated sums and lengths, finally returning maxSum.

C++ 
// C++ implementation to find the sum of nodes
// on the longest path from root to leaf node 
// using level order traversal

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node* left, *right;
    Node(int x) {
        data = x; 
        left = right = nullptr;
    }
};

// Function to calculate the sum of the longest root to 
// leaf path using level order traversal
int sumOfLongRootToLeafPath(Node* root) {
  
    // Base case: if the tree is empty
    if (!root) return 0;

    // Initialize variables to stor
  	// e maximum length and sum
    int maxSum = 0;
    int maxLen = 0;
    
    // Queue for level order traversal, storing pairs of
  	// nodes and their corresponding sum and length
    queue<pair<Node*, pair<int, int>>> q;
  
  	// Starting with the root node, initial
  	// sum, and length
    q.push({root, {root->data, 1}}); 

    while (!q.empty()) {
        auto front = q.front();
        q.pop();

        Node* node = front.first;
        int sum = front.second.first;
        int len = front.second.second;

        // If it's a leaf node, check if we need
      	// to update maxLen and maxSum
        if (!node->left && !node->right) {
            if (len > maxLen) {
                maxLen = len;
                maxSum = sum;
            } else if (len == maxLen && sum > maxSum) {
                maxSum = sum;
            }
        }

        // Push left and right children 
      	// into the queue
        if (node->left) {
            q.push({node->left, {sum + node->left->data, len + 1}});
        }
        if (node->right) {
            q.push({node->right, {sum + node->right->data, len + 1}});
        }
    }

    return maxSum;
}

int main() {
  
    // binary tree formation
    //        4
    //       / \ 
    //      2   5
    //     / \ 
    //    1  3
    Node* root = new Node(4);
    root->left = new Node(2);
    root->right = new Node(5);
    root->left->left = new Node(1);
    root->left->right = new Node(3);
    
    cout << sumOfLongRootToLeafPath(root);

    return 0;
}
Java 
// Java implementation to find the sum of nodes
// on the longest path from root to leaf node 
// using level order traversal

import java.util.LinkedList;
import java.util.Queue;

class Node {
    int data;
    Node left, right;

    Node(int x) {
        data = x;
        left = right = null;
    }
}

class GfG {
  
    // Function to calculate the sum of the longest 
    // root to leaf path using level order traversal
    static int sumOfLongRootToLeafPath(Node root) {
        // Base case: if the tree is empty
        if (root == null) return 0;

        // Initialize variables to store 
      	// maximum length and sum
        int maxSum = 0;
        int maxLen = 0;

        // Queue for level order traversal
        Queue<Object[]> queue = new LinkedList<>();
        queue.add(new Object[]{root, root.data, 1}); 

        while (!queue.isEmpty()) {
            Object[] front = queue.poll();
            Node node = (Node) front[0];
            int sum = (int) front[1];
            int len = (int) front[2];

            // If it's a leaf node, check if we need to
          	// update maxLen and maxSum
            if (node.left == null && node.right == null) {
                if (len > maxLen) {
                    maxLen = len;
                    maxSum = sum;
                } else if (len == maxLen && sum > maxSum) {
                    maxSum = sum;
                }
            }

            // Push left and right children into the queue
            if (node.left != null) {
                queue.add(new Object[]
				{node.left, sum + node.left.data, len + 1});
            }
            if (node.right != null) {
                queue.add(new Object[]
				{node.right, sum + node.right.data, len + 1});
            }
        }

        return maxSum;
    }

    public static void main(String[] args) {
      
        // binary tree formation
        //        4
        //       / \ 
        //      2   5
        //     / \
        //    1  3
        Node root = new Node(4);
        root.left = new Node(2);
        root.right = new Node(5);
        root.left.left = new Node(1);
        root.left.right = new Node(3);
    

        System.out.println(sumOfLongRootToLeafPath(root));
    }
}
Python 
# Python implementation to find the sum of nodes
# on the longest path from root to leaf node 
# using level order traversal

class Node:
    def __init__(self, x):
        self.data = x
        self.left = None
        self.right = None

def sumOfLongRootToLeafPath(root):
  
    # Base case: if the tree is empty
    if not root:
        return 0

    # Initialize variables to store maximum
    # length and sum
    maxSum = 0
    maxLen = 0

    # Queue for level order traversal
    queue = [(root, root.data, 1)]  

    while queue:
        node, sum, length = queue.pop(0)

        # If it's a leaf node, check if we need to 
        # update maxLen and maxSum
        if not node.left and not node.right:
            if length > maxLen:
                maxLen = length
                maxSum = sum
            elif length == maxLen and sum > maxSum:
                maxSum = sum

        # Push left and right children into 
        # the queue
        if node.left:
            queue.append((node.left, sum + node.left.data, length + 1))
        if node.right:
            queue.append((node.right, sum + node.right.data, length + 1))

    return maxSum

if __name__ == "__main__":
  
    # binary tree formation
	#        4
    #       / \ 
    #      2   5
    #     / \ 
    #    1   3
    root = Node(4)
    root.left = Node(2)
    root.right = Node(5)
    root.left.left = Node(1)
    root.left.right = Node(3)
    
    print(sumOfLongRootToLeafPath(root))
C# 
// C# implementation to find the sum of nodes
// on the longest path from root to leaf node 
// using level order traversal

using System;
using System.Collections.Generic;

class Node {
    public int data;
    public Node left, right;

    public Node(int x) {
        data = x;
        left = right = null;
    }
}

class GfG {
  
    // Function to calculate the sum of the longest 
    // root to leaf path using level order traversal
    static int sumOfLongRootToLeafPath(Node root) {
      
        // Base case: if the tree is empty
        if (root == null) return 0;

        // Initialize variables to store
      	// maximum length and sum
        int maxSum = 0;
        int maxLen = 0;

        // Queue for level order traversal
        Queue<Tuple<Node, int, int>> queue = 
          new Queue<Tuple<Node, int, int>>();
        queue.Enqueue(Tuple.Create(root, root.data, 1));  

        while (queue.Count > 0) {
            var front = queue.Dequeue();
            Node node = front.Item1;
            int sum = front.Item2;
            int len = front.Item3;

            // If it's a leaf node, check if we need
          	// to update maxLen and maxSum
            if (node.left == null && node.right == null) {
                if (len > maxLen) {
                    maxLen = len;
                    maxSum = sum;
                } else if (len == maxLen && sum > maxSum) {
                    maxSum = sum;
                }
            }

            // Push left and right children into the queue
            if (node.left != null) {
                queue.Enqueue
                (Tuple.Create(node.left, sum + node.left.data, len + 1));
            }
            if (node.right != null) {
                queue.Enqueue
                (Tuple.Create(node.right, sum + node.right.data, len + 1));
            }
        }

        return maxSum;
    }

   static void Main() {
      
        // binary tree formation
        //        4
        //       / \ 
        //      2   5
        //     / \ 
        //    1   3 
        Node root = new Node(4);
        root.left = new Node(2);
        root.right = new Node(5);
        root.left.left = new Node(1);
        root.left.right = new Node(3);
        Console.WriteLine(sumOfLongRootToLeafPath(root));
    }
}
JavaScript 
// JavaScript implementation to find the sum of nodes
// on the longest path from root to leaf node
// using level order traversal

class Node {
    constructor(x) {
        this.data = x;
        this.left = null;
        this.right = null;
    }
}

function sumOfLongRootToLeafPath(root) {

    // Base case: if the tree is empty
    if (!root) return 0;

    // Initialize variables to store 
    // maximum length and sum
    let maxSum = 0;
    let maxLen = 0;

    // Queue for level order traversal
    const queue = [[root, root.data, 1]]; 

    while (queue.length) {
        const [node, sum, length] = queue.shift();

        // If it's a leaf node, check if we need to 
        // update maxLen and maxSum
        if (!node.left && !node.right) {
            if (length > maxLen) {
                maxLen = length;
                maxSum = sum;
            } else if (length === maxLen && sum > maxSum) {
                maxSum = sum;
            }
        }

        // Push left and right children into the queue
        if (node.left) {
            queue.push
            ([node.left, sum + node.left.data, length + 1]);
        }
        if (node.right) {
            queue.push
            ([node.right, sum + node.right.data, length + 1]);
        }
    }
    
    return maxSum;
}

//        4
//       / \ 
//      2   5
//     / \ 
//    1  3 
const root = new Node(4);
root.left = new Node(2);
root.right = new Node(5);
root.left.left = new Node(1);
root.left.right = new Node(3);

console.log(sumOfLongRootToLeafPath(root));

Output
9

[Expected Approach] Using Recursive - O(n) Time and O(h) Space

The idea is to initializes two variables to track the maximum path length and sum in a binary tree, recursively traverses the tree, adding node values to a running sum and incrementing the path length. When a null node is reached, function checks if the current path length is greater than the stored maximum. if so, function updates both the length and sum. If the lengths are equal, function updates the sum if the current sum is greater. Finally, function returns the maximum sum of the longest path from the root to a leaf.

Illustration:

C++ 
// C++ implementation to find the sum of nodes
// on the longest path from root to leaf node

#include <bits/stdc++.h>
using namespace std;

class Node {
  	
  	public:
    int data;
    Node* left, *right;
  	Node(int x) {
     	data = x; 
      	left = right = nullptr;
    }
};

void sumOfRootToLeaf(Node* root, int sum, int len, 
                     int& maxLen, int& maxSum) {
  
    // Base case: if the current node is null
    if (!root) {
      
        // Checking if the current path has a longer length 
        // and update maxLen and maxSum accordingly
        if (len > maxLen) {
            maxLen = len;
            maxSum = sum;
        }
        // If the lengths are equal, check if the current sum is 
        // greater and update maxSum if necessary
        else if (len == maxLen && sum > maxSum) {
            maxSum = sum;
        }
        return;
    }

    // Recursively calculating the sum of
    // the left and right subtrees
    sumOfRootToLeaf(root->left, sum + root->data, len + 1, maxLen, maxSum);
    sumOfRootToLeaf(root->right, sum + root->data, len + 1, maxLen, maxSum);
}

// Function to calculate the sum of the longest root to leaf path
int sumOfLongRootToLeafPath(Node* root) {
  
    // Base case: if the tree is empty
    if (!root) return 0;

    // Initializing the variables to store the maximum length and sum
    int maxSum = INT_MIN, maxLen = 0;

    // Calling the utility function
    sumOfRootToLeaf(root, 0, 0, maxLen, maxSum);

    // Returning the maximum sum
    return maxSum;
}


int main() {
  
    // binary tree formation
    //        4
    //       / \ 
    //      2   5
    //     / \ 
    //    1   3 
    Node* root = new Node(4);
    root->left = new Node(2);
    root->right = new Node(5);
    root->left->left = new Node(1);
    root->left->right = new Node(3);

    cout << sumOfLongRootToLeafPath(root);

    return 0;
}
Java 
// Java implementation to find the sum of nodes
// on the longest path from root to leaf node
class Node {
    int data;
    Node left, right;

    Node(int x) {
        data = x;
        left = right = null;
    }
}
class GfG {
    static void sumOfRootToLeaf(Node root, int sum,
                                int length, int[] maxLen,
                                int[] maxSum) {
      
        // Base case: if the current node is null
        if (root == null) {
          
            // Checking if the current path has a longer
            // length and update maxLen and maxSum
            // accordingly
            if (length > maxLen[0]) {
                maxLen[0] = length;
                maxSum[0] = sum;
            }
          
            // If the lengths are equal, check if the
            // current sum is greater and update maxSum if
            // necessary
            else if (length == maxLen[0]
                     && sum > maxSum[0]) {
                maxSum[0] = sum;
            }
            return;
        }

        // Recursively calculating the sum of
        // the left and right subtrees
        sumOfRootToLeaf(root.left, sum + root.data,
                        length + 1, maxLen, maxSum);
        sumOfRootToLeaf(root.right, sum + root.data,
                        length + 1, maxLen, maxSum);
    }

    // Function to calculate the sum of the longest root to
    // leaf path
    static int sumOfLongRootToLeafPath(Node root) {
      
        // Base case: if the tree is empty
        if (root == null)
            return 0;

        // Initializing the variables to 
      	// store the maximum length and sum
        int[] maxSum = { Integer.MIN_VALUE };
        int[] maxLen = { 0 };

        // Calling the utility function
        sumOfRootToLeaf(root, 0, 0, maxLen, maxSum);

        // Returning the maximum sum
        return maxSum[0];
    }

    public static void main(String[] args) {

      // binary tree formation
        //        4
        //       / \ 
        //      2   5
        //     / \ 
        //    1   3 
        
        Node root = new Node(4);
        root.left = new Node(2);
        root.right = new Node(5);
        root.left.left = new Node(1);
        root.left.right = new Node(3);
        
        System.out.println(sumOfLongRootToLeafPath(root));
    }
}
Python 
# Python implementation to find the sum of nodes
# on the longest path from root to leaf node

class Node:
    def __init__(self, x):
        self.data = x
        self.left = None
        self.right = None

def sumOfRootToLeaf(root, sum, length, maxLen, maxSum):
  
    # Base case: if the current node is null
    if not root:
      
        # Checking if the current path has a longer length 
        # and update maxLen and maxSum accordingly
        if length > maxLen[0]:
            maxLen[0] = length
            maxSum[0] = sum
            
        # If the lengths are equal, check if the current sum is 
        # greater and update maxSum if necessary
        elif length == maxLen[0] and sum > maxSum[0]:
            maxSum[0] = sum
        return

    # Recursively calculating the sum of
    # the left and right subtrees
    sumOfRootToLeaf(root.left, sum + root.data, length + 1, maxLen, maxSum)
    sumOfRootToLeaf(root.right, sum + root.data, length + 1, maxLen, maxSum)

# Function to calculate the sum of the longest root to leaf path
def sumOfLongRootToLeafPath(root):
  
    # Base case: if the tree is empty
    if not root:
        return 0

    # Initializing the variables to store
    # the maximum length and sum
    maxSum = [-float('inf')]
    maxLen = [0]

    # Calling the utility function
    sumOfRootToLeaf(root, 0, 0, maxLen, maxSum)

    # Returning the maximum sum
    return maxSum[0]


if __name__ == "__main__":
  
    # binary tree formation
    #        4
    #       / \ 
    #      2   5
    #     / \ 
    #    1   3
    root = Node(4)
    root.left = Node(2)
    root.right = Node(5)
    root.left.left = Node(1)
    root.left.right = Node(3)

    print(sumOfLongRootToLeafPath(root))
C# 
// C# implementation to find the sum of nodes
// on the longest path from root to leaf node

using System;
class Node {
	public int data;
    public Node left, right;

    public Node(int x) {
    	data = x;
        left = right = null;
	}
}

class GfG {

    static void sumOfRootToLeaf(Node root, int sum, 
                                int length, ref int maxLen, ref int maxSum) {
      
        // Base case: if the current node is null
        if (root == null) {
          
            // Checking if the current path has a longer length 
            // and update maxLen and maxSum accordingly
            if (length > maxLen) {
                maxLen = length;
                maxSum = sum;
            }
          
            // If the lengths are equal, check if the current sum is 
            // greater and update maxSum if necessary
            else if (length == maxLen && sum > maxSum) {
                maxSum = sum;
            }
            return;
        }

        // Recursively calculating the sum of
        // the left and right subtrees
        sumOfRootToLeaf(root.left, sum + root.data, length + 1, ref maxLen, ref maxSum);
        sumOfRootToLeaf(root.right, sum + root.data, length + 1, ref maxLen, ref maxSum);
    }

    // Function to calculate the sum of the longest
  	// root to leaf path
    static public int sumOfLongRootToLeafPath(Node root) {
      
        // Base case: if the tree is empty
        if (root == null) return 0;

        // Initializing the variables to store the
      	// maximum length and sum
        int maxSum = int.MinValue;
        int maxLen = 0;

        // Calling the utility function
        sumOfRootToLeaf(root, 0, 0, ref maxLen, ref maxSum);

        // Returning the maximum sum
        return maxSum;
    }

    static void Main(string[] args) {
      
        // binary tree formation
        //        4
        //       / \ 
        //      2   5
        //     / \ 
        //    1   3
        
        Node root = new Node(4);
        root.left = new Node(2);
        root.right = new Node(5);
        root.left.left = new Node(1);
        root.left.right = new Node(3);
       
        Console.WriteLine(sumOfLongRootToLeafPath(root));
    }
}
JavaScript 
// JavaScript implementation to find the sum of nodes
// on the longest path from root to leaf node

class Node {
    constructor(x) {
        this.data = x;
        this.left = null;
        this.right = null;
    }
}

function sumOfRootToLeaf(root, sum, length, maxLen, maxSum) {

    // Base case: if the current node is null
    if (!root) {
    
        // Checking if the current path has a longer length 
        // and update maxLen and maxSum accordingly
        if (length > maxLen[0]) {
            maxLen[0] = length;
            maxSum[0] = sum;
        }
        
        // If the lengths are equal, check if the current sum is 
        // greater and update maxSum if necessary
        else if (length === maxLen[0] && sum > maxSum[0]) {
            maxSum[0] = sum;
        }
        return;
    }

    // Recursively calculating the sum of 
    // the left and right subtrees
    sumOfRootToLeaf(root.left, sum + root.data, length + 1, maxLen, maxSum);
    sumOfRootToLeaf(root.right, sum + root.data, length + 1, maxLen, maxSum);
}

// Function to calculate the sum of the longest
// root to leaf path
function sumOfLongRootToLeafPath(root) {

    // Base case: if the tree is empty
    if (!root) return 0;

    // Initializing the variables to store the
    // maximum length and sum
    let maxSum = [-Infinity];
    let maxLen = [0];

    // Calling the utility function
    sumOfRootToLeaf(root, 0, 0, maxLen, maxSum);

    // Returning the maximum sum
    return maxSum[0];
}

// binary tree formation
//        4
//       / \ 
//      2   5
//     / \ 
//    1   3 
const root = new Node(4);
root.left = new Node(2);
root.right = new Node(5);
root.left.left = new Node(1);
root.left.right = new Node(3);

console.log(sumOfLongRootToLeafPath(root));

Output
9
Comment
Article Tags:
Tree
DSA
Traversal

Explore