Find the Sum of Nodes on the Longest Path from the Root to the Leaf Node

Introduction

You should master trees to ace your coding interview for a position in software engineering. They are also essential to many other data structures and regularly come up in coding interviews.

Let's look at a common tree question of finding the sum of nodes on the longest path from the root to the leaf node.

Problem Statement

Ninja has come to visit his girlfriend in her town. Ninja will take her for a long drive through the city to impress her. The town is divided into N equal rose garden areas(N nodes) connected by N-1 roadways(N-1 edges). Each garden contains a different number of red roses(node’s value). There is no self-connecting route.

Ninja’s girlfriend is fond of red roses. Surprisingly, Ninja has come to know that the amount of an effect he will have on her depends entirely on time he will spend with her throughout the journey.

Assume that each road linking two distinct garden areas is the same length. Ninja will start his long drive from his girlfriend’s house(root node). 

If he takes her on the longest route, his girlfriend will be impressed by him. He would also like to give all of the red roses collected by driving down the longest road.

Help Ninja discover the number of red roses on the longest path.

In simpler terms, we need to calculate the sum of nodes on the longest path from the root node to the leaf node.

When two or more paths compete to be the longest, the path with the maximum sum of nodes is considered.

Constraints:

• 1 ≤ Nuber of nodes ≤ 100000
• 1 ≤ Value of nodes ≤ 100000

Sample Examples

Input:

Output:

The sum of nodes on the longest part from root to leaf node is 15.

Explanation:

The longest root to leaf path includes the highlighted nodes 4 -> 6 -> 2-> 3 having the sum of (4 + 6 + 2+ 3) = 15.

Input:

Output:

The sum of nodes on the longest part from root to leaf node is 23.

Explanation:

We have the three longest root-to-leaf paths, which include 
nodes 4 -> 8 ->1->10
nodes 4 -> 5 ->3->7
nodes 4 -> 5 ->3->9
The path with the maximum number of nodes is considered in this situation.
So our output includes the highlighted nodes having the sum of (4 + 8 + 1+ 10) = 23.

Approach 1

We can break down this  problem into two small problems:

• Find the maximum sum in a binary tree from the root node to any leaf node.
• Print the binary tree's root-to-leaf path with the highest sum.

We will recursively calculate the sum of nodes on the longest path from the root to the leaf node.

Algorithm

1. We will create a recursive function to find the sum of nodes on the longest path.
   1. We will pass the root element, current sum, current length, maximum length, and maximum sum as arguments of the recursive function.
   2. If the root will be equal to NULL and if the maximum length will be smaller than the current length:
      1. We will update the maximum length and the maximum sum.
         
          
2. Recursively call the function for the Left Subtree.
   1. As arguments, we will pass the root-left element, current sum+ root-data, current length +1, maximum length, and maximum sum.
      
       
3. Similarly, call the function recursively for the Right Subtree.
   1. As arguments, we will pass the root-right element, current sum+ root-data, current length +1, maximum length, and maximum sum.

Implementation

#include <bits/stdc++.h>
using namespace std;
// Nodes of the binary tree
struct Nodes {
          int data;
          Nodes* left, *right;
};


// function to get a new node
Nodes* newNode(int data)
{
         // allocating memory for the node
           Nodes* getNode = (Nodes*)malloc(sizeof(Nodes));

           getNode->data = data;
           getNode->left = getNode->right = NULL;
           return getNode;
}


// function to find the sum of nodes on the
// longest path from root to leaf node
void SumlongestPath(Nodes* root, int crnt_sum, int length, int& maxLen, int& maxSum)
{
           // if true,traverse a root to leaf path
           if (!root) {
                          // update maximum length and maximum sum
                          if (maxLen < length) {
                                        maxLen = length;
                                        maxSum = crnt_sum;
                          } else if (maxLen == length && maxSum < crnt_sum)
                                        maxSum = crnt_sum;
                    return;
}


// recursive function for left subtree
SumlongestPath(root->left, crnt_sum + root->data, length + 1, maxLen, maxSum);

// recursive function for right subtree
SumlongestPath(root->right, crnt_sum + root->data, length + 1, maxLen, maxSum);
}

// utility function to find the sum 
int SumlongestPathUtil(Nodes* root)
{
            // if tree is NULL, then the sum is 0
             if (!root)
                       return 0;
             int maxSum = INT_MIN, maxLen = 0;

             // finding the maximum sum 'maxSum' for the
            // maximum length root to leaf path
    SumlongestPath(root, 0, 0, maxLen, maxSum);
         // required maximum sum
            return  maxSum;
}


// Driver code
int main()
{
         // binary tree formation
         Nodes* root = newNode(4);
         root->left = newNode(8);
         root->right = newNode(5);  
         root->left->left = newNode(2); 
         root->left->right = newNode(1);
         root->right->left = newNode(3); 
         root->right->right = newNode(9); 
         root->left->right->left = newNode(6);


         cout << "The sum of nodes on the longest part from root to leaf node is "<< SumlongestPathUtil(root);
         return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

The sum of nodes on the longest part from root to leaf node is 19

You can also try this code with Online C++ Compiler

Run Code

Complexity Analysis

• Time Complexity: The time complexity of the above solution is O(n). Since we need linear time for traversing the tree in a postorder manner.
   
• Space Complexity: We need an extra O(n) space to store the subproblems' value. So, the space complexity of the above solution is O(n).

Here n is the size of the binary tree.