LeetCode 333: Largest BST Subtree Solution

Master LeetCode problem 333 (Largest BST Subtree), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

333. Largest BST Subtree

Medium

Dynamic Programming Tree Depth-First Search Binary Search Tree Binary Tree

Problem Explanation

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

Create a helper function that takes a node, its minimum and maximum values, and returns the size of the BST rooted at that node.
In the helper function, recursively call it on the left and right children of the current node.
Check if the current node's value is within the range specified by the minimum and maximum values.
If the current node is a valid BST node, update the size of the BST rooted at the current node.
Update the size of the largest BST found so far if needed.
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.

Solution Code

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;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 333 (Largest BST Subtree)?

This page provides optimized solutions for LeetCode problem 333 (Largest BST Subtree) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 333 (Largest BST Subtree)?

The time complexity for LeetCode 333 (Largest BST Subtree) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 333 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 333 in Java, C++, or Python.

Back to LeetCode Solutions