Maximum Sum BST in Binary Tree: II - C++ Solution and Time Complexity Analysis

Input: root = [1,4,3,2,4,2,5,null,null,null,null,null,null,4,6]
Output: 20
Explanation: Maximum sum in a valid Binary search tree is obtained in root node with key equal to 3.

Input: root = [4,3,null,1,2]
Output: 2
Explanation: Maximum sum in a valid Binary search tree is obtained in a single root node with key equal to 2.

Input: root = [-4,-2,-5]
Output: 0
Explanation: All values are negatives. Return an empty BST.

Input: root = [2,1,3]
Output: 6

Input: root = [5,4,8,3,null,6,3]
Output: 7

Understanding the Problem

The core challenge of this problem is to identify the sub-trees within a binary tree that are valid Binary Search Trees (BSTs) and then calculate the sum of their nodes. The goal is to find the maximum sum among all such sub-trees.

This problem is significant in various applications such as database indexing, memory management, and more, where BST properties are leveraged for efficient data retrieval and storage.

Potential pitfalls include incorrectly identifying BSTs or missing edge cases where sub-trees might not be valid BSTs.

Approach

To solve this problem, we need to traverse the tree and check each sub-tree to see if it is a valid BST. A naive approach would involve checking every possible sub-tree, but this would be highly inefficient.

Instead, we can use a post-order traversal (left-right-root) to gather information about each sub-tree and determine if it is a BST. This allows us to efficiently calculate the sum of nodes for valid BSTs and keep track of the maximum sum encountered.

Naive Solution

The naive solution involves checking every possible sub-tree to see if it is a BST and then calculating the sum of its nodes. This approach is not optimal due to its high time complexity.

Optimized Solution

We can optimize the solution using a post-order traversal. During the traversal, we can gather information about the sub-trees, such as their minimum and maximum values, sum of nodes, and whether they are valid BSTs. This information can be used to determine if the current sub-tree is a valid BST and calculate its sum.

Algorithm

Here is a step-by-step breakdown of the optimized algorithm:

1. Perform a post-order traversal of the tree.
2. For each node, gather information about its left and right sub-trees (minimum value, maximum value, sum of nodes, and whether they are valid BSTs).
3. Determine if the current node forms a valid BST with its left and right sub-trees.
4. If it is a valid BST, calculate the sum of its nodes and update the maximum sum if necessary.
5. Return the maximum sum encountered.

Code Implementation

#include <iostream>
#include <climits>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    struct SubTreeInfo {
        bool isBST;
        int sum;
        int minVal;
        int maxVal;
    };
    
    int maxSumBST(TreeNode* root) {
        int maxSum = 0;
        postOrderTraversal(root, maxSum);
        return maxSum;
    }
    
    SubTreeInfo postOrderTraversal(TreeNode* node, int &maxSum) {
        if (!node) {
            return {true, 0, INT_MAX, INT_MIN};
        }
        
        SubTreeInfo leftInfo = postOrderTraversal(node->left, maxSum);
        SubTreeInfo rightInfo = postOrderTraversal(node->right, maxSum);
        
        if (leftInfo.isBST && rightInfo.isBST && node->val > leftInfo.maxVal && node->val < rightInfo.minVal) {
            int currentSum = node->val + leftInfo.sum + rightInfo.sum;
            maxSum = max(maxSum, currentSum);
            return {true, currentSum, min(node->val, leftInfo.minVal), max(node->val, rightInfo.maxVal)};
        } else {
            return {false, 0, 0, 0};
        }
    }
};

// Example usage
int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(4);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(2);
    root->left->right = new TreeNode(4);
    root->right->left = new TreeNode(2);
    root->right->right = new TreeNode(5);
    root->right->right->left = new TreeNode(4);
    root->right->right->right = new TreeNode(6);
    
    Solution sol;
    cout << "Maximum Sum BST: " << sol.maxSumBST(root) << endl;
    
    return 0;
}

Complexity Analysis

The time complexity of the optimized solution is O(n), where n is the number of nodes in the tree. This is because we perform a single post-order traversal of the tree.

The space complexity is O(h), where h is the height of the tree. This is due to the recursive call stack used during the traversal.

Edge Cases

Potential edge cases include:

• Empty tree: The output should be 0.
• All negative values: The output should be 0 if no valid BSTs are found.
• Single node tree: The output should be the value of the single node.

These edge cases are handled by the algorithm as it checks for null nodes and validates BST properties at each step.

Testing

To test the solution comprehensively, consider the following test cases:

• Simple trees with a few nodes.
• Large trees with mixed positive and negative values.
• Edge cases such as empty trees and single node trees.

Testing frameworks such as Google Test can be used to automate and validate the test cases.

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

• Break down the problem into smaller sub-problems.
• Use tree traversal techniques to gather information about sub-trees.
• Validate the properties of BSTs at each step.
• Practice solving similar problems to improve problem-solving skills.

Conclusion

In this blog post, we discussed the problem of finding the maximum sum of keys in any sub-tree of a binary tree that is also a BST. We explored a naive solution and an optimized solution using post-order traversal. We also provided a detailed C++ implementation and analyzed the complexity of the solution. By understanding and practicing such problems, you can improve your problem-solving skills and algorithmic thinking.

Additional Resources

For further reading and practice, consider the following resources:

• LeetCode Problem
• GeeksforGeeks: Binary Search Tree
• Coursera: Data Structures