Given a binary tree in which each node element contains a number. Find the maximum possible sum from one leaf node to another.

Given a binary tree in which each node element contains a number. Find the maximum possible sum from one leaf node to another.

Input Format:

The first line of input contains the number of test cases T. For each test case, there will be only a single line of input which is a string representing the tree as described below: 

1. The values in the string are in the order of level order traversal of the tree where, numbers denote node values, and a character “N” denotes NULL child.

2. For example:
   

For the above tree, the string will be: 1 2 3 N N 4 6 N 5 N N 7 N
There are multiple test cases. For each test case, the function will be called individually.

For Input:

2

3 4 5 -10 4

-15 5 6 -8 1 3 9 2 -3 N N N N N 0 N N N N 4 -1 N N 10 N

Your Output is:

16

27

// { Driver Code Starts

#include <bits/stdc++.h>

using namespace std;

// Tree Node

struct Node {

    int data;

    Node *left;

    Node *right;

    Node(int val) {

        data = val;

        left = right = NULL;

    }

};

// Function to Build Tree

Node *buildTree(string str) {

    // Corner Case

    if (str.length() == 0 || str[0] == 'N') return NULL;

    // Creating vector of strings from input

    // string after spliting by space

    vector<string> ip;

    istringstream iss(str);

    for (string str; iss >> str;) ip.push_back(str);

    // Create the root of the tree

    Node *root = new Node(stoi(ip[0]));

    // Push the root to the queue

    queue<Node *> queue;

    queue.push(root);

    // Starting from the second element

    int i = 1;

    while (!queue.empty() && i < ip.size()) {

        // Get and remove the front of the queue

        Node *currNode = queue.front();

        queue.pop();

        // Get the current Node's value from the string

        string currVal = ip[i];

        // If the left child is not null

        if (currVal != "N") {

            // Create the left child for the current Node

            currNode->left = new Node(stoi(currVal));

            // Push it to the queue

            queue.push(currNode->left);

        }

        // For the right child

        i++;

        if (i >= ip.size()) break;

        currVal = ip[i];

        // If the right child is not null

        if (currVal != "N") {

            // Create the right child for the current Node

            currNode->right = new Node(stoi(currVal));

            // Push it to the queue

            queue.push(currNode->right);

        }

        i++;

    }

    return root;

}

int maxPathSum(Node *);

int main() {

    int tc;

    scanf("%d ", &tc);

    while (tc--) {

        string treeString;

        getline(cin, treeString);

        Node *root = buildTree(treeString);

        cout << maxPathSum(root) << "\n";

    }

    return 0;

}// } Driver Code Ends

/*

struct Node

{

    int data;

    struct Node* left;

    struct Node* right;

    

    Node(int x){

        data = x;

        left = right = NULL;

    }

};

*/

int find(Node *root,int &ans)

{

     if(root==NULL)

    return 0;

 if(!root->left&&!root->right)

 return root->data;

 int a=find(root->left,ans);

 int b=find(root->right,ans);

 if(root->left&&root->right)

  {

      ans=max(ans,a+b+root->data);

      return max(a,b)+root->data;

  }

  if(root->left)

  return a+root->data;

  else

  return b+root->data;

   

}

int maxPathSum(Node* root)

{ 

    // code here 

    int ans=INT_MIN;

    if(root==NULL)

    return 0;

  find(root,ans);

  return ans;

    

}