Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Understanding the Problem
3.
Brute Force
4.
Intuition
5.
Algorithm
6.
Code
6.1.
Input
6.2.
Output
6.3.
Time Complexity
6.4.
Space Complexity
7.
Bonus
8.
Code
8.1.
Input
8.2.
Output
8.3.
Time Complexity
8.4.
Space Complexity
9.
Key Takeaways
Last Updated: Mar 27, 2024

Maximum sum path from the leaf to leaf(Extend it to any node to any node)

Author Saksham Gupta
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Binary trees are an all-time favorite topic for coding interviews. Thus, it is important to master such a topic. There are a large number of questions out there on binary trees, but if you get the hold of the topic right, you are good to go. Today we will be seeing one such frequently asked question in coding interviews, i.e., Maximum Sum Path From the Leaf to Leaf in a Binary Tree. In this blog, we will be discussing the problem and its solutions from scratch. You can practice the question at our platform Coding Ninjas Studio and return to this blog if you feel stuck.

Understanding the Problem

We have been given a non-empty binary tree with a non-negative integer value for each node, and we have to return the maximum possible path (sum of all the nodes in the path) between any two leaves of the given tree, including leaf nodes. The maximum path sum may or may not pass through the tree's root.

We have to return -1 if there is just one leaf node in the tree.

 

Let's try to visualize the problem better by the following example.

 

                                                                                                  Source: source

Now, if we take out all the possible cases (path sum) from leaves, we have 14 (from leaf 5 to leaf 6), 23(From leaf 7 to leaf 6 ), 22(From leaf 7 to leaf 5). In the above example, the answer returned would be 23 as this is the maximum sum possible among all the paths (7 + 4 + 2 + 1 + 3 + 6) that is from leaf 7 to 6.

Now let’s look at the approach towards the problem.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Brute Force

Now the brute force approach for this problem is very simple. We will calculate all possible answers, i.e., path sum from every leaf to every other leaf, and then return the maximum path sum among them. But this method will cost us a lot of time and, time is money in coding, so let’s now see the efficient approach for the problem.

Intuition

The way we are thinking about solving this problem is that we will calculate the maximum path sum leaf to leaf in constant time. Our idea here is to start from the bottom of the tree and then return each node's maximum sum node-to-leaf path to its parent node. We calculate the maximum sum path rooted at each node and update the max sum during the traversal.

It will become more clear once we discuss the algorithm.

Algorithm

We will declare the following functions.

  1. 'findMaxSumPath()': This will return our final answer. In this function, we will declare a variable 'MAX_SUM_PATH' and will initialize it to -1. This variable will store the final answer, i.e., the maximum path sum from leaf to leaf. Inside this function, we will call the function' findMaxSumPathHelper()', which will take two parameters i,e, tree's root and the variable 'maxPathSum' by reference.

 2. 'findMaxSumPathHelper()': This is where all the magic is going to happen. It is going to be a recursive function that will accept two parameters:

  1. 'ROOT' is the root of our tree.
  2. 'MAX_PATH_SUM' is our final answer.


Recursive Case : 

  1. We will make two calls to this function, i.e., left and right subtree of the 'ROOT' node, and store their answers in the variables 'MAX_SUM_LEFT_PATH' (maximum sum along the path starting from the current node('ROOT') and ending at a leaf node in the left subtree) and the 'MAX_SUM_RIGHT_PATH' (maximum sum along the path starting from the current node('ROOT') and ending at a leaf node in the right subtree) respectively.
  2. Then we will update the value of 'MAXPATHSUM' as:

'MAX_PATH_SUM' = max('MAX_PATH_SUM' , 'MAX_SUM_LEFT_PATH' + ' MAX_SUM_RIGHT_PATH' + 'ROOT'->val)

 3. Then we will return the maximum sum in the subtree starting from the current node(root) to leaf i.e. max(‘MAX_SUM_LEFT_PATH',      ‘MAX_SUM_RIGHT_PATH’') + ‘ROOT’->val

Below is the implementation of the function.

Code

#include <iostream>
#include <queue>
using namespace std;

// Binary Tree Node Class.
template <typename T>
class BinaryTreeNode
{
public:
    T val;
    BinaryTreeNode<T> *left;
    BinaryTreeNode<T> *right;

    BinaryTreeNode(T val)
    {
        this->val = val;
        left = NULL;
        right = NULL;
    }
};

long long int findMaxSumPathHelper(BinaryTreeNode<int> *root, long long int &maxPathSum)
{
    if (root == NULL)
    {
        return -1;
    }

    if (root->left == NULL && root->right == NULL)
    {
        return root->val;
    }

    // Variable to store the maximum sum of the path from the current node to leaf in the left subtree.
    long long int maxSumLeftPath = findMaxSumPathHelper(root->left, maxPathSum);

    // Variable to store the maximum sum of the path from the current node to leaf in the right subtree.
    long long int maxSumRightPath = findMaxSumPathHelper(root->right, maxPathSum);

    // If the current node has both children, update the value of maxPathSum.
    if (root->left != NULL && root->right != NULL)
    {
        maxPathSum = max(maxPathSum, maxSumLeftPath + maxSumRightPath + root->val);
        return max(maxSumLeftPath, maxSumRightPath) + root->val;
    }
    else if (root->left == NULL)
    {
        return maxSumRightPath + root->val;
    }
    else
    {
        return maxSumLeftPath + root->val;
    }
}

long long int findMaxSumPath(BinaryTreeNode<int> *root)
{
    // Variable to store the maximum sum of the path between two leaves for the given tree.
    long long int maxPathSum = -1;

    // Calling 'findMaxSumPathHelper()' function to calculate 'MAX_PATH_SUM'.
    findMaxSumPathHelper(root, maxPathSum);
  
    return maxPathSum;
}

// Function to take user input.
BinaryTreeNode<int> *takeInput()
{
    int rootData;
    cin >> rootData;
  
    if (rootData == -1)
    {
        return NULL;
    }

    BinaryTreeNode<int> *root = new BinaryTreeNode<int>(rootData);
    queue<BinaryTreeNode<int> *> q;
    q.push(root);
  
    while (!q.empty())
    {
        BinaryTreeNode<int> *currentNode = q.front();
        q.pop();
        int leftChild, rightChild;

        cin >> leftChild;
        if (leftChild != -1)
        {
            BinaryTreeNode<int> *leftNode = new BinaryTreeNode<int>(leftChild);
            currentNode->left = leftNode;
            q.push(leftNode);
        }

        cin >> rightChild;
        if (rightChild != -1)
        {
            BinaryTreeNode<int> *rightNode = new BinaryTreeNode<int>(rightChild);
            currentNode->right = rightNode;
            q.push(rightNode);
        }
    }
    return root;
}

int main()
{
    BinaryTreeNode<int> *root = takeInput();
    cout << findMaxSumPath(root) << endl;
}

Input

1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

 

The input tree would look something like this.

Output

23

Time Complexity

O(N), where ‘N’ is the number of nodes in the tree.

Since we are traversing the entire tree only once so in total, we will be traversing every node once. Thus the time complexity is O(N).

Space Complexity

O(N), where 'N' is the number of nodes in the tree.

The recursive stack will take O(H) space where ‘H’ is the height of the tree. In the worst case, H will equal ‘N’ when each node in the tree has only one child(skewed tree). Thus, the space complexity is O(N).

Bonus

Now we can extend the above code to find to maximum path sum between any two nodes, Intuition behind this is very similar to the one we discussed above, so without wasting any time, let's have a look at the algorithm.

  1. Our answer will be stored in the variable 'MAX_SUM', which will store the maximum path sum out of all paths. We will initialize it to INT_MIN. 
  2. We will now create a helper function 'currentPathSum()', that will take two parameters, 'CURRENT_PEAK,' (root node) and 'MAX_SUM',  and will return the maximum sum path from 'CURRENT_PEAK' and its descending nodes. Let us look at the functioning of this function:
    1. If our root node or 'CURRENT_PEAK' is NULL, we will return 0 as this is the maximum sum possible from a NULL Node.
    2. We will make two calls to this function for the left and right child of 'CURRENT_PEAK' and store the answer in 'MAX_PATH_SUM_LEFT' and 'MAX_PATH_SUM_RIGHT,' respectively.
    3. Now we will create a new variable 'CURRENT_SUM' and initialsie it as ('MAX_PATH_SUM_LEFT' + 'MAX_PATH_SUM_RIGHT' + (CURRENT_PEAK->data)).
    4. 'MAX_SUM' will be updated as the maximum of 'MAX_SUM' and 'CURRENT_PATH_SUM'.
    5. Then we will return the sum of 'CURRENT_PEAK_NODE' and the maximum among 'MAX_PATH_SUM_LEFT' and 'MAX_PATH_SUM_RIGHT'. This will be used for calculating the maximum sum path value for the parent nodes.
  3. Return the answer, i.e., ‘MAX_SUM’.


Below is the implementation of the above algorithm.

Code

#include <iostream>
#include <queue>
#include<algorithm>
#include<climits>
using namespace std;

// Binary Tree Node Class.
template <typename T>
class BinaryTreeNode {
  public:
    T data;
    BinaryTreeNode<T>* left;
    BinaryTreeNode<T>* right;

    BinaryTreeNode(T data) {
        this->data = data;
        left = NULL;
        right = NULL;
    }
};


int currentPathSum(BinaryTreeNode<int> *currentPeak, int &maxSum)
{
    // Checking if the current node is NULL.
    if (currentPeak == NULL)
    {
        return 0;
    }

    int maxPathSumLeft = max(currentPathSum(currentPeak->left,
    maxSum), 0);
    int maxPathSumRight = max(currentPathSum(currentPeak->right,
    maxSum), 0);

    int currentSum = maxPathSumLeft + maxPathSumRight +
    (currentPeak->data);

    // Updating the overall maximum sum.
    maxSum = max(currentSum, maxSum);

    return max(maxPathSumLeft, maxPathSumRight) +   
    (currentPeak->data);
}

int maxPathSum(BinaryTreeNode<int> *root)
{
    int maxSum = INT_MIN;

    // Calling the recursive function.
    currentPathSum(root, maxSum);

    // Returning the updated value.
    return maxSum;

}
BinaryTreeNode<int>* takeInput() {
    int rootData;
    cin >> rootData;
    if (rootData == -1) {
        return NULL;
    }
    BinaryTreeNode<int>* root = new BinaryTreeNode<int>(rootData);
    queue<BinaryTreeNode<int>*> q;
    q.push(root);
    while (!q.empty()) {
        BinaryTreeNode<int>* currentNode = q.front();
        q.pop();
        int leftChild, rightChild;

        cin >> leftChild;
        if (leftChild != -1) {
            BinaryTreeNode<int>* leftNode = new
            BinaryTreeNode<int>(leftChild);
            currentNode->left = leftNode;
            q.push(leftNode);
        }

        cin >> rightChild;
        if (rightChild != -1) {
            BinaryTreeNode<int>* rightNode = new
            BinaryTreeNode<int>(rightChild);
            currentNode->right = rightNode;
            q.push(rightNode);
        }
    }
    return root;
}

int main() {
    BinaryTreeNode<int>* root = takeInput();
    cout<<maxPathSum(root);
}

Input

1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

 

The input tree would look something like this

Output

23

Time Complexity

O(N), where ‘N’ is the number of nodes in the tree.

Since we are traversing the entire tree only once, the overall time complexity is O(N).

Space Complexity

O(N), where 'N' is the number of nodes in the tree.

The recursive stack will take O(H) space where ‘H’ is the height of the tree. In the worst case, H will equal ‘N’ when each node in the tree has only one child. Thus, the space complexity is O(N).

Check out this problem - Root To Leaf Path

Key Takeaways

Now you have understood how to find the maximum sum path from the leaf to leaf as well as the maximum path sum from any node to any node in the binary tree. Your adrenaline would be on the next level, But don't worry, we have a solution for that too. Head over to our practice platform Coding Ninjas Studio to practice top problems and many more. Till then, Happy Coding!

Previous article
Count subsequences with GCD equal to X
Next article
Sum of the Length of Paths from Every Node to All Other Nodes
Live masterclass