The algorithm for the maximum sum in a binary tree
The maximum sum in a binary tree is the largest sum that can be found in a path which may start and end at any node in the tree.
Algorithm
-
Use recursion to find the maximum sum in the left and right sub-trees.
-
Compute the maximum of the following four cases:
- Value of root
- Value of root + left sub-tree
- Value of root + right sub-tree
- Value of root + left + right sub-trees
-
If the maximum value (found in step 2) is greater than the global max variable, update the global maximum.
-
Return the maximum of the first three cases.
Return value
The value returned in the last step of the algorithm is the maximum value of only the first three cases (mentioned in step 2). If the fourth case has the maximum value, then the root and its sub-trees are the top of our max sum path (i.e., the root cannot be connected to its parent caller; otherwise, the path would start or end at more than one node).
Implementation
The following is the code for the algorithm described above in C++, Java, and Python.
#include <iostream>#include <algorithm>#include <limits.h>using namespace std;struct Node{Node *left, *right;int val;Node(int v){val = v;left = NULL;right = NULL;}};Node* createTree(){/*3/ \2 20/ / \7 5 -8*/Node* root = new Node(3);// Creating 2nd level:Node* one = new Node(2);Node* two = new Node(20);root->left = one;root->right = two;// Creating 3rd level:Node* three = new Node(7);Node* four = new Node(5);Node* five = new Node(-8);one->left = three;two->left = four;two->right = five;return root;}int findMaxSum(Node* root, int &globalMax){// Reached end of tree:if(root == NULL)return 0;// Find the max sum of children sub-trees recursively:int left = findMaxSum(root->left, globalMax);int right = findMaxSum(root->right, globalMax);// Find max of the first three cases:int returnMax = std::max(std::max(left, right) + root->val, root->val);// Find max of the first four cases to update globalMax:int max = std::max(returnMax, left + right + root->val);// Update globalMax:if(max > globalMax)globalMax = max;// Return returnMax:return returnMax;}int main(){// Create tree:Node* myTree = createTree();// Set globalSum to minimum possible value:int globalMax = INT_MIN;findMaxSum(myTree, globalMax);// Compute and display result:cout << "Maximum possible sum: " << globalMax << endl;return 0;}
Free Resources
