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

Given a binary tree root, the task is to return the maximum sum of all keys of any sub-tree which is also a Binary Search Tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less 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.

Example 1:

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.

Example 2:

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.

Example 3:

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

Example 4:

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

Example 5:

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

Constraints:

Each tree has at most 40000 nodes..
Each node's value is between [-4 * 10^4 , 4 * 10^4].

Understanding the Problem

The core challenge of this problem is to identify the largest sum of keys in any subtree that is a valid Binary Search Tree (BST). A BST is defined by the properties that all nodes in the left subtree are less than the root, and all nodes in the right subtree are greater than the root. Both subtrees must also be BSTs.

This problem is significant in various applications such as database indexing, where BST properties are used to maintain sorted data for efficient retrieval.

Potential pitfalls include incorrectly identifying BSTs or not considering all possible subtrees.

Approach

To solve this problem, we can use a recursive approach to traverse the tree and check for BST properties. A naive solution would involve checking every possible subtree, which is inefficient. Instead, we can use a post-order traversal to gather information about each subtree and determine if it forms a BST.

We will use a helper function that returns multiple values: whether the subtree is a BST, the sum of the subtree, the minimum value in the subtree, and the maximum value in the subtree. This information allows us to efficiently determine if a larger subtree is a BST and calculate its sum.

Algorithm

The algorithm involves a post-order traversal of the tree. For each node, we recursively check its left and right subtrees. We then use the information from these subtrees to determine if the current subtree is a BST and calculate its sum if it is.

Here is a step-by-step breakdown:

Define a helper function that returns a tuple containing whether the subtree is a BST, the sum of the subtree, the minimum value in the subtree, and the maximum value in the subtree.
For each node, recursively call the helper function on its left and right children.
Check if the current node forms a BST with its left and right subtrees using the information returned by the helper function.
If it forms a BST, calculate the sum of the current subtree and update the maximum sum if this sum is greater.
Return the appropriate values to the parent call.

Code Implementation

#include <iostream>
#include <tuple>
#include <algorithm>
#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:
    int maxSumBST(TreeNode* root) {
        int maxSum = 0;
        postOrderTraversal(root, maxSum);
        return maxSum;
    }

private:
    // Helper function to perform post-order traversal and check BST properties
    tuple postOrderTraversal(TreeNode* node, int& maxSum) {
        if (!node) {
            return {true, 0, INT_MAX, INT_MIN}; // Base case: empty subtree
        }

        auto [leftIsBST, leftSum, leftMin, leftMax] = postOrderTraversal(node->left, maxSum);
        auto [rightIsBST, rightSum, rightMin, rightMax] = postOrderTraversal(node->right, maxSum);

        if (leftIsBST && rightIsBST && node->val > leftMax && node->val < rightMin) {
            int currentSum = node->val + leftSum + rightSum;
            maxSum = max(maxSum, currentSum);
            int currentMin = min(node->val, leftMin);
            int currentMax = max(node->val, rightMax);
            return {true, currentSum, currentMin, currentMax};
        } else {
            return {false, 0, 0, 0}; // Not a BST
        }
    }
};

int main() {
    // Example usage:
    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 this approach is O(n), where n is the number of nodes in the tree. This is because we visit each node exactly once during the post-order traversal.

The space complexity is O(h), where h is the height of the tree. This is due to the recursive call stack, which can go as deep as the height of the tree.

Edge Cases

Potential edge cases include:

Empty tree: The function should return 0.
All negative values: The function should return 0 if no positive sum BST exists.
Single node tree: The function should return the value of the single node if it is positive.

These cases are handled by the base case in the helper function and the conditions checking for BST properties.

Testing

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

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

Using a testing framework like Google Test can help automate and manage these test cases effectively.

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

Break down the problem into smaller subproblems.
Use recursive approaches for tree problems, as they naturally fit the structure of trees.
Think about the properties of the data structure (e.g., BST properties) and how they can be used to simplify the problem.
Practice similar problems to build intuition and improve problem-solving skills.

Conclusion

In this blog post, we discussed how to solve the problem of finding the maximum sum BST in a binary tree using a recursive approach. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for improving problem-solving skills and preparing for technical interviews.

Additional Resources

For further reading and practice, consider the following resources: