Maximum Sum Bst In Binary Tree - Leetcode Solution

Problem Statement: Given a binary tree rooted at root, the task is to find the maximum sum BST (subtree) in it. If there is no such subtree, return 0.

A subtree is a BST if:

• The left subtree of a node contains only nodes with keys lesser than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.
• The value of sum of all nodes must be maximum among all BST subtrees.

Solution: We can perform a recursive traversal of the tree in a bottom-up approach. We start by traversing to the left child, then right child, and finally sum up the values of the nodes. While traversing, we also keep track of the minimum and maximum values encountered in the subtree. If the subtree is a valid BST, we calculate its sum and compare it with the maximum sum BST seen so far.

To validate if a subtree is a valid BST, we compare the maximum value of the left subtree with the root node and the minimum value of the right subtree with the root node. If both are satisfied, we calculate the sum of the subtree and compare it with the current maximum sum. We also update the global minimum and maximum values seen so far in the subtree.

At the end, we return the maximum sum seen so far.

Code:

C++ Code:

class Solution { private: struct TreeNodeInfo { bool isBST = false; int sum = 0; int maxVal = -1e9, minVal = 1e9; }; int maxSum = 0;

TreeNodeInfo isValid(TreeNode* root) {
    if (root == nullptr) {
        return TreeNodeInfo();
    }
    
    auto leftNodeInfo = isValid(root->left);
    auto rightNodeInfo = isValid(root->right);
    
    TreeNodeInfo current;
    if (leftNodeInfo.isBST && rightNodeInfo.isBST && 
        leftNodeInfo.maxVal < root->val && rightNodeInfo.minVal > root->val) {
        
        current.isBST = true;
        current.sum = leftNodeInfo.sum + rightNodeInfo.sum + root->val;
        current.minVal = min(root->val, leftNodeInfo.minVal);
        current.maxVal = max(root->val, rightNodeInfo.maxVal);
        
        maxSum = max(maxSum, current.sum);
    }
    return current.isBST ? current : TreeNodeInfo();
}

public: int maxSumBST(TreeNode* root) { isValid(root); return maxSum; } };

Python Code:

class Solution: def init(self): self.max_sum = 0 def maxSumBST(self, root: TreeNode) -> int: def is_valid(root): if not root: return False, 0, float('inf'), -float('inf')

        is_left_bst, left_sum, left_min, left_max = is_valid(root.left)
        is_right_bst, right_sum, right_min, right_max = is_valid(root.right)
        
        if (not root.left or left_max < root.val) and \
        (not root.right or right_min > root.val):
            current_sum = left_sum + right_sum + root.val
            current_min = min(left_min, root.val)
            current_max = max(right_max, root.val)
            self.max_sum = max(self.max_sum, current_sum)
            return True, current_sum, current_min, current_max
        
        return False, 0, float('-inf'), float('inf')
    
    is_valid(root)
    return self.max_sum

Time Complexity: The solution performs a complete traversal of the tree, hence O(n), where n is the number of nodes.

Space Complexity: The solution uses O(h) space on the function call stack, where h is the height of the tree (maximum depth of the recursion). In the worst case, when the tree is skewed, h can be equal to n. Hence, the space complexity can be O(n) in the worst case scenario.

1