Binary Tree: Given a binary tree, find the maximum path sum between two leaves

Problem Statement:

Given a binary tree, find the maximum path sum between two leaves.

Solution Explanation:

The solution needs to consider any path, not only from root to leaf.

That might include from start and end at any node as long as it move downwards.

So for that we need to compute the sum of node + max path on left + max path on right

Time Complexity: O(n)
Space Complexity: O(h)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

struct Node 
{
    int data;
    struct Node *left;
    struct Node *right;
};


struct Node* newNode(int data)
{
    struct Node* newNode = new Node;
    newNode->data = data;
    newNode->left = newNode->right = NULL;

    return (newNode);
}

void display_inorder(Node* root)
{
    if (root == NULL)
        return;

    display_inorder(root->left);
    cout << root->data << " ";
    display_inorder(root->right);
}


void insert_inorder(Node* root, vector<int>& nodes) 
{
    if (root == nullptr) 
    {
        return;
    }
  
    insert_inorder(root->left, nodes);  
    nodes.push_back(root->data);          
    insert_inorder(root->right, nodes); 
}


int result = INT_MIN;

int helper(Node* node) 
{
    if (!node) 
        return 0;

    int left = max(helper(node->left), 0);
    int right = max(helper(node->right), 0);

    result = max(result, node->data + left + right);

    return node->data + max(left, right);
}

int solution(Node* root) 
{

    helper(root);
    return result;
}

int main(void)
{
    /*
     *           10
     *         /    \
     *        8      12
     *       / \    /  \
     *      2   9  11   14
     */
    struct Node* root = newNode(10);
    root->left = newNode(8);
    root->right = newNode(12);
    root->left->left = newNode(2);
    root->left->right = newNode(9);
    root->right->left = newNode(11);
    root->right->right = newNode(14);

    
    
    cout << solution(root);
 
    return 0;
}

Output

53