LeetCode 1373: Maximum Sum BST in Binary Tree Solution

Master LeetCode problem 1373 (Maximum Sum BST in Binary Tree), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1373. Maximum Sum BST in Binary Tree

Hard

Dynamic Programming Tree Depth-First Search Binary Search Tree Binary Tree

Problem Explanation

Explanation:

To solve this problem, we need to traverse the binary tree in a bottom-up manner while keeping track of certain properties of each subtree. We will perform a recursive depth-first search (DFS) on the tree nodes. For each node, we will check if it forms a valid binary search tree (BST) and calculate the sum of keys in that subtree. We will keep track of the maximum sum found so far.

Algorithm:

Define a helper function that takes a node as input and returns a tuple containing four values:
- Sum of keys in the subtree rooted at this node.
- Minimum key value in the subtree rooted at this node.
- Maximum key value in the subtree rooted at this node.
- Whether the subtree rooted at this node is a valid BST.
Perform a post-order traversal of the tree using the helper function.
Update the maximum sum found so far if the current subtree has a greater sum and is a valid BST.
Return the maximum sum found.

Time Complexity: O(N) where N is the number of nodes in the tree. Space Complexity: O(H) where H is the height of the tree.

Solution Code

class Solution {
    int maxSum = 0;
    
    public int maxSumBST(TreeNode root) {
        postOrder(root);
        return maxSum;
    }
    
    private int[] postOrder(TreeNode node) {
        if (node == null) {
            return new int[]{0, Integer.MAX_VALUE, Integer.MIN_VALUE, 1};
        }
        
        int[] left = postOrder(node.left);
        int[] right = postOrder(node.right);
        
        if (left[3] == 1 && right[3] == 1 && node.val > left[2] && node.val < right[1]) {
            int sum = node.val + left[0] + right[0];
            maxSum = Math.max(maxSum, sum);
            return new int[]{sum, Math.min(node.val, left[1]), Math.max(node.val, right[2]), 1};
        } else {
            return new int[]{0, 0, 0, 0};
        }
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1373 (Maximum Sum BST in Binary Tree)?

This page provides optimized solutions for LeetCode problem 1373 (Maximum Sum BST in Binary Tree) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1373 (Maximum Sum BST in Binary Tree)?

The time complexity for LeetCode 1373 (Maximum Sum BST in Binary Tree) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1373 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1373 in Java, C++, or Python.

Back to LeetCode Solutions