Maximum Sum BST in Binary Tree — LeetCode 1373 Python Solution

The problem

Given a binary tree root, 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.

Example

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.

Python solution

# 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:
        def dfs(root: Optional[TreeNode]) -> tuple:
            if root is None:
                return 1, inf, -inf, 0
            lbst, lmi, lmx, ls = dfs(root.left)
            rbst, rmi, rmx, rs = dfs(root.right)
            if lbst and rbst and lmx < root.val < rmi:
                nonlocal ans
                s = ls + rs + root.val
                ans = max(ans, s)
                return 1, min(lmi, root.val), max(rmx, root.val), s
            return 0, 0, 0, 0

        ans = 0
        dfs(root)
        return ans

Complexity

Pattern: Tree Traversal

Choose the order — preorder, inorder, postorder, level — and the problem solves itself. LeetCode 1373. Maximum Sum BST in Binary Tree is filed here because LeetCode tags it Tree, Binary Tree and Binary Search Tree, which is the vocabulary this hub collects.

The tree traversal guide has the Python template for the pattern and the 225 LeetCode problems that use it.

Related problems