using namespace std;
class node
{
public:
int data;
node *right;
node *left;
node(int d)
{
this->data = d;
this->left = NULL;
this->right = NULL;
}
};
class solution
{
public:
int global_max = INT_MIN;
int findMaxSum(node *root)
{
if (root == NULL)
{
return 0;
}
int left1 = findMaxSum(root->left);
int right1 = findMaxSum(root->right);
int case1 = root->data;
int case2 = root->data + left1;
int case3 = root->data + right1;
int case4 = root->data + left1 + right1;
global_max = max(case1, max(case2, max(case3, max(global_max, case4))));
return ((max(left1, max(right1, 0))) + root->data);
}
void maxSum(node *root)
{
int sum=findMaxSum(root);
cout << "Max sum= " << sum << endl;
}
};
node* treeFromArray(int *arr,int start,int end)
{
if (start > end)
{
return NULL;
}
int mid = (start + end) / 2;
node *root = new node(arr[mid]);
root->left = treeFromArray(arr, start, mid - 1);
root->right = treeFromArray(arr, mid + 1, end);
return root;
}
void bfs(node *root)
{
queue<node *> q;
q.push(root);
q.push(NULL);
while (!q.empty())
{
node *f = q.front();
if (f == NULL)
{
cout << endl;
q.pop();
if (!q.empty())
{
q.push(NULL);
}
}
else
{
q.pop();
cout << f->data << " ";
if (f->left)
{
q.push(f->left);
}
if (f->right)
{
q.push(f->right);
}
}
}
return;
}
int main()
{
int arr[] = { 1, 2, 3, 0, 5, 6, 7 };
int n = sizeof(arr) / sizeof(int);
node *root = treeFromArray(arr, 0, n - 1);
bfs(root);
solution s;
s.maxSum(root);
return 0;
}