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 N1 roadways(N1 edges). Each garden contains a different number of red roses(node’s value). There is no selfconnecting 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 roottoleaf 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 roottoleaf 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

We will create a recursive function to find the sum of nodes on the longest path.
 We will pass the root element, current sum, current length, maximum length, and maximum sum as arguments of the recursive function.

If the root will be equal to NULL and if the maximum length will be smaller than the current length:

We will update the maximum length and the maximum sum.

We will update the maximum length and the maximum sum.

Recursively call the function for the Left Subtree.

As arguments, we will pass the rootleft element, current sum+ rootdata, current length +1, maximum length, and maximum sum.

As arguments, we will pass the rootleft element, current sum+ rootdata, current length +1, maximum length, and maximum sum.

Similarly, call the function recursively for the Right Subtree.
 As arguments, we will pass the rootright element, current sum+ rootdata, 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;
}
Output:
The sum of nodes on the longest part from root to leaf node is 19
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.