#1373

Maximum Sum BST in Binary Tree

candidate master · 1520 · lc hard +32 · verified · 46.6% accepted · 2,968 likes · top 31%

Description

Given a binary tree root, find the subtree that forms a valid BST and has the greatest possible sum of node keys. Return that maximum sum.

A BST requires: left subtree values are all strictly less than the root's key, right subtree values are all strictly greater, and both subtrees are also valid BSTs.

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.

Code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxSumBST(self, root: Optional[TreeNode]) -> int:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxSumBST(self, root: Optional[TreeNode]) -> int: