-
Notifications
You must be signed in to change notification settings - Fork 46
/
maxSumPath.cpp
85 lines (71 loc) · 1.93 KB
/
maxSumPath.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <iostream>
#include "basicTreeTemplate.h"
// Prints the path from the node to the Target node.
void getPath(Node *root, int target)
{
if (!root)
return;
// If cuurent node value if lesser than target node value, print node value and then go right
if (target > root->data)
{
cout << root->data << " ";
getPath(root->right, target);
}
// else , print node value and then go left
else
{
cout << root->data << " ";
getPath(root->left, target);
}
}
Node *maxSumPath(Node *root)
{
// Varible initializations.. 'static' as we want them to be unchanged throughout the recursive tree calls.
static Node *target;
static int index;
static int count, trackPathSum = INT_MIN;
static int *path = new int[30];
if (!root)
return 0;
// Storing the Data nodes in an array.
path[index] = root->data;
index++;
// Increasing the sum.
count += root->data;
// If it is a leaf node.
if (!root->left && !root->right)
{
// If the Current sum is greater than previous sum, then set this node as the target node.
if (count > trackPathSum)
{
trackPathSum = count;
target = root;
}
}
maxSumPath(root->left);
maxSumPath(root->right);
// Decreasing the sum by the node's value when backtracking.
count -= root->data;
index--;
// Return the Target Node.
return target;
}
int main()
{
Node *root = nullptr;
insertNode(root, 50);
insertNode(root, 60);
insertNode(root, 70);
insertNode(root, 80);
insertNode(root, 90);
insertNode(root, 55);
insertNode(root, 10);
insertNode(root, 5);
insertNode(root, 40);
// Create a Temporary Node to store the resultant node..
Node *temp;
temp = maxSumPath(root);
// Shows the Path from the root to that Temp node.
getPath(root, temp->data);
cout << '\n';
}