maxSumPath

using namespace std;

#include<iostream>
#include<cstdio>
#include<vector>

struct Node {

    Node() {
        value = 0;
        left = NULL;
        right = NULL;
        timesVisited = 0;
    }

    int value;
    Node* left;
    Node* right;
    int timesVisited;

};

void constructTree(Node* head) {

    if (head == NULL) {
        return ;
    }

    head->value = 10;
    head->left=new Node;
    head->right=new Node;


    head->left->value = 5;
    head->left->left=new Node;
    head->left->right=new Node;
    head->left->left->value = 1;
    head->left->right->value=8;

    head->right->value = 40;
    head->right->left=new Node();
    head->right->right=new Node();
    head->right->left->value=30;
    head->right->left->left = new Node();
    head->right->left->left->value = 20;
    head->right->right->value=50;
}

int maxSum(Node* head,int sum) {

  if(head == NULL) {
    return sum;
  }

  int left = maxSum(head->left, sum + head->value) ;
  int right = maxSum(head->right, sum + head->value);

  return left>right?left:right;

}

bool foundPath = false;
vector<Node*> sumVec;

void maxPath(Node* parent, Node* head, int maxSum, int k) {

 if(head == NULL) {

    if(k == maxSum) {
      bool foundBefore = false;

      if(!sumVec.empty()) {

        for(int i = 0; i < sumVec.size(); i++ ) {
          Node* node = sumVec[i];

          if(node == parent) {
            foundBefore = true;
            break;
          }
        }
      }

      if(!foundBefore) {
        foundPath = true;
        sumVec.push_back(parent);
      }
    }
  return;
 }

  maxPath(head, head->left, maxSum, k +  head->value);

  if(foundPath) {
    cout << head->value << " ";
    return ;
  }

  maxPath(head, head->right, maxSum, k + head->value);

  if(foundPath) {
    cout << head->value << " ";
    return ;
  }
}


int main() {

  Node* head ;
  head = new Node;
  constructTree(head);

  int maxSumTree = maxSum(head, 0);

  cout << maxSumTree << endl;
  do {
    foundPath = false;
    maxPath(NULL, head, maxSumTree, 0);
    cout << endl;
  }while(foundPath);

  cin>>maxSumTree;


  return 0;


}