Find root to leaf path whose sum is maximum in a binary tree

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.

Tree with max sum path.
A binary tree with max sum path is [24, 16, 12]

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 2^h 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 O(n). There are several other algorithms to solve this problem, but not with better than O(n) complexity. Full solution with driver code is as shown below.

// Output
Result is: 
24-->16-->12-->NULL

Complexity: O(n)

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!.