Binary Tree: Maximum path sum in a binary tree

Problem Statement:

Given a binary tree, find the maximum path.

Path does not need to pass through the root.

A path can include each node at most once.

Example:

Input:

    /*
     *           10
     *         /    \
     *        8      12
     *       / \    /  \
     *      2   9  11   14
     */

Output:

14 -> 12 -> 10 = 36

Solution Explanation:

We have given 2 conditions:

1. Path might not pass through the root node

2. Path can include each node at most once.

This means, the path should move downwards.

So we need to split into left and right sub trees.

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

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
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);
}


int solution(Node* node, int result) 
{
    if (!node) 
    {
        return 0;
    }

    // Compute max sum of left and right subtree path
    int leftSum = max(0, solution(node->left, result));
    int rightSum = max(0, solution(node->right, result));

    result = max(result, leftSum + rightSum + node->data);

    return max(leftSum, rightSum) + node->data;
}

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);

    int result = 0;
    
    cout << solution(root, result);
    
    return 0;
}

Output

36