Finding the Maximum Sum BST in Binary Tree involves analyzing a given binary tree and identifying the specific subtree that satisfies all properties of a Binary Search Tree while yielding the highest possible sum of its node values. A valid binary search tree requires that all left descendants have strictly smaller values than the parent, and all right descendants have strictly greater values than the parent. The goal is to return the largest sum found among all valid binary search tree subtrees within the main tree structure.
Example 1
Input: root = [4,3,null,1,2]
Output: 2
Explanation: The root node has a value of 4, but its left child 3 has a right child 2, which violates the binary search tree property since 2 is less than 3. The largest valid binary search tree in this structure is the single leaf node 2, giving a maximum sum of 2.
Example 2
Input: root = [-4,-2,-5]
Output: 0
Explanation: All nodes have negative values. A valid binary search tree can also be completely empty. In cases where the maximum possible sum of any physical subtree is negative, choosing an empty subtree yields a sum of 0, making 0 the correct output.
Brute Force Approach
Think of a large corporation with multiple departments and branches. An auditor wants to find the single most profitable branch, but only if that branch perfectly follows strict hierarchical reporting rules. In a brute-force audit, the inspector visits every single manager in the company. For each manager, they investigate the entire branch from top to bottom to verify if the rules are followed. If the branch passes the inspection, the total profit of that branch is calculated and compared against the best profit found so far.
In terms of trees, this means traversing to every node in the binary tree. For each node, a separate check is performed to see if the subtree rooted there forms a valid binary search tree. If it is valid, the sum of its nodes is calculated.
Algorithm
A global variable named maxTotalSum is initialized to zero to store the highest valid sum encountered during the traversals, accounting for the fact that an empty tree provides a sum of zero.
The tree is traversed by visiting each node starting from the root. The termination condition is reached when a null node is encountered, at which point the current recursive path ends.
For every node visited, a separate validation function is executed to confirm if the entire subtree bounded by the current node satisfies the strict binary search tree properties.
If the subtree is validated successfully, another helper function is triggered to compute the sum of all node values within this specific subtree.
The computed sum is compared against maxTotalSum, and the variable is updated if the new sum is larger, ensuring the absolute maximum is preserved by the end of the traversal.
Dry Run
Maximum Sum in BST Brute Dry Run
Solution
#include <bits/stdc++.h>using namespace std;// Definition for a binary tree nodestruct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {}};class Solution {private: // Validates if a given subtree adheres to strict binary search tree rules bool isValidBST(TreeNode* root, long long minVal, long long maxVal) { if (root == NULL) return true; // Ensure the current node value falls within the strictly allowed boundaries if (root->val <= minVal || root->val >= maxVal) return false; // Recursively validate both left and right subtrees with updated boundaries return isValidBST(root->left, minVal, root->val) && isValidBST(root->right, root->val, maxVal); } // Accumulates the sum of all node values within a confirmed valid subtree int calculateSum(TreeNode* root) { if (root == NULL) return 0; return root->val + calculateSum(root->left) + calculateSum(root->right); } // Traverses the entire tree to test every single node as a potential root void traverseAndCheck(TreeNode* root, int& maxTotalSum) { if (root == NULL) return; // If the current subtree is perfectly valid, compute and compare its total sum if (isValidBST(root, LONG_MIN, LONG_MAX)) { int currentSum = calculateSum(root); maxTotalSum = max(maxTotalSum, currentSum); } traverseAndCheck(root->left, maxTotalSum); traverseAndCheck(root->right, maxTotalSum); }public: // Main entry function that initializes tracking variables and triggers traversal int maxSumBST(TreeNode* root) { int maxTotalSum = 0; traverseAndCheck(root, maxTotalSum); return maxTotalSum; }};// Driver code starts hereint main() { TreeNode* root = new TreeNode(4); root->left = new TreeNode(3); root->left->left = new TreeNode(1); root->left->right = new TreeNode(2); Solution obj; int result = obj.maxSumBST(root); cout << "Maximum Sum of BST is: " << result << endl; return 0;}Complexity Analysis
Time Complexity: O(N2), N is the number of nodes in the tree, for each node we are traversing the whole subtree this makes N computations per node.
Space Complexity: O(N), N is the number of nodes in the tree, for recursion stack.
Optimal Approach
The previous approach is inefficient because it performs highly repetitive tasks. Checking the top node involves re-checking all the bottom nodes that were already investigated in previous steps. This redundancy is removed by processing the tree from the bottom upwards.
Returning to the corporate audit example, rather than having the top executive personally investigate every employee repeatedly, a bottom-up reporting system is established. The lowest-level employees calculate their own profits and confirm their rule compliance, then hand a short summary report to their direct manager.
The manager looks at the reports from their teams. If the teams followed the rules, and the manager is correctly positioned above them, the manager simply adds their numbers together and passes a new combined report further up. If a rule is broken at any level, that manager passes up a "failed" report, and the executives above immediately know the branch is invalid without re-auditing it. If you want to understand this in detail, check our guide on Post-order Traversal.
Algorithm
A structured state object is conceptualized to hold four key metrics for any subtree: whether it is a valid binary search tree, its minimum value, its maximum value, and the sum of its nodes.
A post-order traversal function is executed, ensuring that both left and right children are fully processed before evaluating the parent node. The termination condition occurs when a null node is reached, which safely returns a valid state representing an empty tree with a sum of zero.
Upon receiving the state reports from the left and right children, a strict condition is checked: both children must be valid binary search trees, the current node's value must be strictly greater than the maximum value in the left subtree, and it must be strictly less than the minimum value in the right subtree.
If this condition is fully satisfied, the current subtree is deemed valid. A new sum is calculated by adding the left sum, right sum, and the current node value. A global tracking variable is updated if this newly calculated sum is the highest seen so far.
A successful state report is passed upwards containing the new minimum, new maximum, and the total sum. If the validation condition fails, an invalid state report is passed upwards to immediately invalidate all parent subtrees.
Dry Run
Maximum Sum in BST Optimal Dry Run
Solution
#include <bits/stdc++.h>using namespace std;// Definition for a binary tree nodestruct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {}};// Custom structure to hold all necessary metrics for bottom-up reportingstruct SubtreeState { bool isBST; int minNode; int maxNode; int sum;};class Solution {private: // Evaluates the tree from the bottom upwards using post-order traversal SubtreeState postOrder(TreeNode* root, int& maxTotalSum) { if (root == NULL) { // An empty tree is perfectly valid with extreme bounds and zero sum return {true, INT_MAX, INT_MIN, 0}; } SubtreeState left = postOrder(root->left, maxTotalSum); SubtreeState right = postOrder(root->right, maxTotalSum); // Ensure both branches are valid and the current node perfectly bridges them if (left.isBST && right.isBST && root->val > left.maxNode && root->val < right.minNode) { int currentSum = left.sum + right.sum + root->val; maxTotalSum = max(maxTotalSum, currentSum); // The new minimum and maximum must account for single leaf nodes return { true, min(root->val, left.minNode), max(root->val, right.maxNode), currentSum }; } // If rules are broken, return a completely invalid state to disable parents return {false, 0, 0, 0}; }public: // Core function initiating the optimal traversal process int maxSumBST(TreeNode* root) { int maxTotalSum = 0; postOrder(root, maxTotalSum); return maxTotalSum; }};// Driver code starts hereint main() { TreeNode* root = new TreeNode(4); root->left = new TreeNode(3); root->left->left = new TreeNode(1); root->left->right = new TreeNode(2); Solution obj; int result = obj.maxSumBST(root); cout << "Maximum Sum of BST is: " << result << endl; return 0;}Complexity Analysis
Time Complexity: O(N), N is the number of nodes in the tree, performing O(1) mathematical validations at every single node keeps the execution fully linear.
Space Complexity: O(N), N is the number of nodes in the tree, keeping track of the subtree traversal routes requires memory proportional to the maximum tree depth.
Interview follow-up Questions
When validating a single leaf node, the algorithm needs to compare its value against its children. An empty left child returns a maximum boundary of negative infinity, ensuring the leaf node is correctly recognized as larger than it. An empty right child returns a minimum boundary of positive infinity, ensuring the leaf node is smaller than it.
Be the first to add a comment.