Problem statement

https://binarysearch.com/problems/Largest-Binary-Search-Subtree-in-Value/

Solution

Equal to Leetcode 1373. Maximum Sum BST in Binary Tree.

Complexity

It is O(n) for time and O(h) for space.

Code

class Solution:
    def solve(self, root):
        def dfs(node):
            if not node: return 0, True, -inf, inf
            
            s_L, bst_L, max_L, min_L = dfs(node.left)
            s_R, bst_R, max_R, min_R = dfs(node.right)
            if bst_L and bst_R and max_L < node.val < min_R:
                v = node.val + s_L + s_R
                self.ans = max(self.ans, v)
                return v, True, max(max_R, node.val), min(node.val, min_L)
            
            return 0, False, -inf, inf
        
        self.ans = 0
        dfs(root)
        return self.ans