Given a binary tree with all positive integer nodes, we need to find the path from the root to a leaf whose sum is maximum in all root to leaf paths of the binary tree.
The above diagram shows a simple binary tree with the maximum sum path [24, 16, 12].
This algorithm needs an actual path list, a max path list, a sum variable at each node, and a max sum integer variable to compare with the sum at each node. Every path starts with root and ends with its child node.
So, A binary tree with height ‘h’ does have at max paths. We check if both left and right children are NULL then that node can be called as child node.
if(root->left == NULL && root->right == NULL)
{
// Node is child
// check current sum and current path with max path.
}
Below is the most efficient algorithms to solve this problem.
/*
* @Inputs: root node,
* sum,
* path and resultPath (maxPath)
*
* @Output: void
*/
void maxRootToLeafSumUtil(
struct Node *root,
int sum,
list<struct Node *> path,
list<struct Node *> &resultPath)
{
if (root == NULL)
{
return;
}
static int maxSum;
path.push_back(root);
sum += root->data;
if (sum > maxSum)
{
maxSum = sum;
}
if (root->left == NULL && root->right == NULL)
{
if (sum == maxSum)
{
resultPath = path;
}
return;
}
maxRootToLeafSumUtil(root->left, sum, path, resultPath);
maxRootToLeafSumUtil(root->right, sum, path, resultPath);
}
Above solution works with complexity of . There are several other algorithms to solve this problem, but not with better than complexity. Full solution with driver code is as shown below.
// Output
Result is:
24-->16-->12-->NULL
Complexity:
Hence, it is the solution for finding the max length sum of root to leaf path in a binary tree. If you know any better solution or found any errors in the above algorithm, please let readers know by commenting below. Cheers!.