How do you solve Maximum Sum BST in Binary Tree on LeetCode?

Maximum Sum BST in Binary Tree (LeetCode #1373) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(h) space complexity. Key insight: Understanding the properties of BSTs is crucial for solving this problem.

What is the brute force solution for Maximum Sum BST in Binary Tree?

The brute force approach for Maximum Sum BST in Binary Tree is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves checking every subtree of the binary tree to see if it forms a valid Binary Search Tree (BST). If it does, we calculate its sum and keep track of the maximum sum found. The optimal Optimal Solution approach improves this to O(n).

What are the interview tips for Maximum Sum BST in Binary Tree?

Explain your thought process clearly while coding. Consider edge cases and discuss them with the interviewer. Optimize your solution after presenting the brute-force approach.

What are common mistakes when solving Maximum Sum BST in Binary Tree?

Not properly checking the BST conditions, leading to incorrect sums. Failing to handle edge cases, such as empty trees or all negative values.

#1373

Maximum Sum BST in Binary Tree

Hard

Dynamic ProgrammingTreeDepth-First SearchBinary Search TreeBinary TreeDepth-First SearchBinary Search Tree properties

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(h)

💡

Intuition

Time O(n)Space O(h)

The optimal approach uses a depth-first search (DFS) to traverse the tree while simultaneously checking if each subtree is a valid BST. We maintain the sum, min, and max values of each subtree to efficiently determine its validity.

⚙️

Algorithm

3 steps

1Step 1: Use a DFS function that returns a tuple containing whether the subtree is a BST, its sum, its minimum value, and its maximum value.
2Step 2: For each node, check if its left and right subtrees are valid BSTs and if the current node's value is greater than the maximum value of the left subtree and less than the minimum value of the right subtree.
3Step 3: If valid, calculate the sum and update the maximum sum found.

solution.py22 lines

1# Full working Python code
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def maxSumBST(self, root: TreeNode) -> int:
10        self.max_sum = 0
11        def dfs(node):
12            if not node:
13                return (True, 0, float('inf'), float('-inf'))
14            leftIsBST, leftSum, leftMin, leftMax = dfs(node.left)
15            rightIsBST, rightSum, rightMin, rightMax = dfs(node.right)
16            if leftIsBST and rightIsBST and leftMax < node.val < rightMin:
17                sum_bst = leftSum + rightSum + node.val
18                self.max_sum = max(self.max_sum, sum_bst)
19                return (True, sum_bst, min(leftMin, node.val), max(rightMax, node.val))
20            return (False, 0, 0, 0)
21        dfs(root)
22        return self.max_sum

ℹ

Complexity note: The time complexity is linear because we visit each node exactly once. The space complexity is O(h) due to the recursion stack, where h is the height of the tree.

1Understanding the properties of BSTs is crucial for solving this problem.
2Using a DFS approach allows us to efficiently check and calculate sums in one pass.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.