Introduction
Binary trees are the specialized version of generic trees where every node can have at most only two children named the left child and right child of a binary tree. In this blog, we will be discussing a problem where we have to find out the maximum possible sum of the path between any two leaves of a given binary tree. Let us understand this problem clearly with the below example:
(Also see, Data Structures)
Let us find the path sum between all leaves of this binary tree and then we will select the maximum among them as our output.
Path Between The Leaves |
Sum |
9->4->7 |
20 |
9->4->6->3 |
22 |
9->4->6->5->2 |
26 |
7->4->6->3 |
20 |
7->4->6->5->2 |
24 |
3->6->5->2 |
16 |
Out of all the above six paths, path 9->4->6->5->2 is the maximum sum path with a sum of 26. Hence the output will be 26.
I hope the problem is crystal clear to you now. So now is the time to move towards its solution.
Recommended: Do try the Problem yourself before moving on to the solution
Method 1
In this approach, for every node we will be finding out the maximum sum node-to-leaf path from the left and right subtrees:
Step 1: We’ll be finding the maximum sum from the current node to a leaf node in the left subtree of the traversed node.
Step 2: Likewise, find the maximum sum from the current node to a leaf node in the right subtree of the traversed node.
Step 3: Add the values obtained in steps 1 and 2 and also add the data of the traversed node to get the maximum sum node-to-leaf path using the left and right subtrees.
Step 4: Compare it with the maximum value obtained so far and update the maximum value.
Let’s see this approach in code:
C++ code for Finding Maximum Sum Path in a Binary Tree
#include <bits/stdc++.h>
using namespace std;
class TreeNode
{
public:
//data members
int val;
TreeNode *left, *right;
//constructor
TreeNode()
{
left = NULL;
right = NULL;
}
};
// Function to calculate the maximum sum from node to leaf.
long long int findMaxSumNodeToLeaf(TreeNode *root)
{
if (root == NULL)
{
return 0;
}
long long int maxSumLeftPath = findMaxSumNodeToLeaf(root->left);
long long int maxSumRightPath = findMaxSumNodeToLeaf(root->right);
long long int maxSumFromNodeToLeaf = root->val + max(maxSumLeftPath, maxSumRightPath);
return maxSumFromNodeToLeaf;
}
// Function to calculate the maximum sum of path between two leaves that passes through a node.
long long int findMaxSumPathViaNode(TreeNode *root)
{
if (root == NULL)
{
return -1;
}
// Variable to store the maximum sum of path between two leaves for the given tree.
long long int maxPathSum = -1;
// Variable to store the max length of path from left child to leaf.
long long int maxSumPathFromLeft = findMaxSumNodeToLeaf(root->left);
// Variable to store the max length of path from right child to leaf.
long long int maxSumPathFromRight = findMaxSumNodeToLeaf(root->right);
if (root->left != NULL && root->right != NULL)
{
long long int maxSumPathViaNode = maxSumPathFromLeft + maxSumPathFromRight + root->val;
maxPathSum = max(maxPathSum, maxSumPathViaNode);
}
maxPathSum = max({maxPathSum, findMaxSumPathViaNode(root->left), findMaxSumPathViaNode(root->right)});
return maxPathSum;
}
long long int findMaxSumPath(TreeNode *root)
{
return findMaxSumPathViaNode(root);
}
//function for the creation of a new node
TreeNode *createNode(int data)
{
TreeNode *newNode = new TreeNode();
newNode->val = data;
return newNode;
}
int main()
{
//creating the binary tree
TreeNode *root = createNode(5);
root->left = createNode(6);
root->right = createNode(2);
root->left->left = createNode(4);
root->left->right = createNode(3);
root->left->left->left = createNode(9);
root->left->left->right = createNode(7);
cout << "Maximum path sum of the binary tree is:" << findMaxSumPath(root);
return 0;
}
Output:
Maximum path sum of the binary tree is:26Complexity Analysis
Time Complexity: The time complexity is O(N^2) where N is the number of nodes in the binary tree. For every node in the tree, we are calculating the maximum sum node-to-leaf path of its left subtree and right subtree. This takes O(N) time and since there are ‘N’ nodes, the final complexity is O(N * N) = O(N^2).
Space Complexity: The space complexity will be O(N), where N is the number of nodes in the binary tree.
The recursive stack will take O(H) space where H is the height of the tree. In the worst case, H will be equal to N, when each node in the tree has only one child. Thus, the space complexity is O(N).
569+ registered 
