Largest BST Subtree

Intuition

This problem could be solved by using DFS (inorder traversal) with some additional variables.

The basic theory of this problem is that, for every node in a Binary Search Tree, nodes in its left sub-tree is less than the node, and node i its right sub-tree is greater than its left sub-tree. And we would use this theory and DFS to solve this problem.

Solution


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

class Solution:
    def largestBSTSubtree(self, root: TreeNode) -> int:
        if root is None:
            return 0
        return self._helper(root)['size']

    def _helper(self, node):
        """
        :return: [min, max, is_bst, size]
        """
        is_bst = True
        if node.left is None:
            l = {
                    'min': node.val,
                    'max': node.val,
                    'is_bst': True,
                    'size': 0
                }
        else:
            l = self._helper(node.left)
            is_bst = is_bst and l['is_bst'] and l['max'] < node.val

        if node.right is None:
            r = {
                    'min': node.val,
                    'max': node.val,
                    'is_bst': True,
                    'size': 0
                }
        else:
            r = self._helper(node.right)
            is_bst = is_bst and r['is_bst'] and r['min'] > node.val

        if not is_bst:
            return {
                    'min': 0,
                    'max': 0,
                    'is_bst': False,
                    'size': max(l['size'], r['size'])
                    }
        return {
                'min': l['min'],
                'max': r['max'],
                'is_bst': True,
                'size': l['size'] + r['size'] + 1
                }