LeetCode 333: Largest BST Subtree

Explanation

To find the largest Binary Search Tree (BST) subtree in a given binary tree, we need to perform a depth-first search on each node to determine if its subtree is a valid BST. We can do this recursively by passing the range of valid values for each subtree node. We will keep track of the size of the largest valid BST found so far and update it whenever a larger valid BST is encountered.

Algorithm

1. Create a helper function that takes a node, its minimum and maximum values, and returns the size of the BST rooted at that node.
2. In the helper function, recursively call it on the left and right children of the current node.
3. Check if the current node's value is within the range specified by the minimum and maximum values.
4. If the current node is a valid BST node, update the size of the BST rooted at the current node.
5. Update the size of the largest BST found so far if needed.
6. Return the size of the BST rooted at the current node.

Time Complexity

The time complexity of this algorithm is O(n), where n is the number of nodes in the binary tree.

Space Complexity

The space complexity of this algorithm is O(h), where h is the height of the binary tree.

class Solution {
    int maxBSTSize = 0;
    
    public int largestBSTSubtree(TreeNode root) {
        if (root == null) return 0;
        
        isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
        
        return maxBSTSize;
    }
    
    private int isBST(TreeNode node, int min, int max) {
        if (node == null) return 0;
        
        if (node.val <= min || node.val >= max) {
            return -1;
        }
        
        int left = isBST(node.left, min, node.val);
        int right = isBST(node.right, node.val, max);
        
        if (left == -1 || right == -1) return -1;
        
        int size = 1 + left + right;
        maxBSTSize = Math.max(maxBSTSize, size);
        
        return size;
    }
}