Leetcode 0333. Largest BST Subtree

Problem statement

https://leetcode.com/problems/largest-bst-subtree/

Solution

Use auxiliary function dfs(node), which return 3 parameters: the smallest, the biggest values for subtree with root at this node and number of nodes in this subtree if it is BST and $-\infty$ in opposite case. Also keep global variable for the biggest subtree found so far.

Complexity

Time complexity is $O(n)$, space complexity is $O(h)$.

Code

class Solution:
    def largestBSTSubtree(self, root):
        def dfs(node):
            if not node: return (float("inf"), -float("inf"), 0)
            min_l, max_l, size_l = dfs(node.left)
            min_r, max_r, size_r = dfs(node.right)
            cand = -float("inf")
            if max_l < node.val < min_r:
                cand = size_l + size_r + 1
                self.ans = max(self.ans, cand)
                
            return (min(node.val, min_l), max(node.val, max_r), cand)
        
        self.ans = 0
        dfs(root)
        return self.ans