BinarySearch 0129 Largest Binary Search Subtree in Nodes

Problem statement

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

Solution

Variation of 1373. Maximum Sum BST in Binary Tree, but here we need number of nodes, not sum of them. The idea is to keep 4 values: number of nodes, indicator if we have BST, min value, max value.

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 = 1 + s_L + s_R
                self.ans = max(self.ans, (v, node), key = lambda x: x[0])
                return v, True, max(max_R, node.val), min(node.val, min_L)
            
            return 0, False, -inf, inf
        
        self.ans = (0, None)
        dfs(root)
        return self.ans[1]