Largest BST Subtree

Problem: Largest BST Subtree

We can use depth-first search to solve this problem. At each node, we want to know whether its left subtree and right subtree are BSTs. Either of them not being a BST will make the whole tree not a BST. If both are BSTs, we need to verify whether the tree rooted at current node is a BST by checking the biggest number in left subtree and smallest number in right subtree. If the current tree is a BST, we can update the answer by size of left subtree plus right subtree plus one.

Code in Python:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def largestBSTSubtree(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root: return 0
        self.res = 0
        def dfs(root):
            if not root.left and not root.right:
                self.res = max(self.res, 1)
                return root.val, root.val, 1
            if not root.left:
                rl, rr, rs = dfs(root.right)
                if rs and rl > root.val:
                    self.res = max(self.res, rs+1)
                    return root.val, rr, rs+1
                else:
                    return None, None, None
            if not root.right:
                ll, lr, ls = dfs(root.left)
                if ls and lr < root.val:
                    self.res = max(self.res, ls+1)
                    return ll, root.val, ls+1
                else:
                    return None, None, None
            ll, lr, ls = dfs(root.left)
            rl, rr, rs = dfs(root.right)
            if ls and rs and lr < root.val and rl > root.val:
                self.res = max(self.res, ls+1+rs)
                return ll, rr, ls+1+rs
            return None, None, None
        dfs(root)
        return self.res