> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0333-largest-bst-subtree.md).

# 0333. Largest BST Subtree

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

## Description

Given the root of a binary tree, find the largest subtree, which is also a Binary Search Tree (BST), where the largest means subtree has the largest number of nodes.

A **Binary Search Tree (BST)** is a tree in which all the nodes follow the below-mentioned properties:

* The left subtree values are less than the value of their parent (root) node's value.
* The right subtree values are greater than the value of their parent (root) node's value.

**Note:** A subtree must include all of its descendants.

**Follow up:** Can you figure out ways to solve it with O(n) time complexity?

**Example 1:**

![](https://assets.leetcode.com/uploads/2020/10/17/tmp.jpg)

```
**Input:** root = [10,5,15,1,8,null,7]
**Output:** 3
**Explanation:** The Largest BST Subtree in this case is the highlighted one. The return value is the subtree's size, which is 3.
```

**Example 2:**

```
**Input:** root = [4,2,7,2,3,5,null,2,null,null,null,null,null,1]
**Output:** 2
```

**Constraints:**

* The number of nodes in the tree is in the range `[0, 104]`.
* `-104 <= Node.val <= 104`

## ac

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int maxSize = Integer.MIN_VALUE;

    public int largestBSTSubtree(TreeNode root) {
        if (root == null) return 0;
        valid(root);
        return maxSize;
    }

    public List<Integer> valid(TreeNode node) {

        List<Integer> res = new ArrayList<>();
        // exit
        if (node == null) {
            res.add(0);
            res.add(Integer.MAX_VALUE);
            res.add(Integer.MIN_VALUE);
            return res;
        }

        List<Integer> left = valid(node.left);
        List<Integer> right = valid(node.right);

        if (left == null || right == null) return null;
        if (left.get(2) < node.val && node.val < right.get(1)) {

            int size = left.get(0) + 1 + right.get(0);
            maxSize = Math.max(maxSize, size);
            res.add(size);
            int min = node.left == null ? node.val : left.get(1);
            int max = node.right == null ? node.val : right.get(2);
            res.add(min);
            res.add(max);
            return res;
        }

        return null;
    }
}

/*
Divide&Conquer. 1) return multiple information: size, min, max, if (left.get(2) < node.val && node.val < right.get(1)) we meet a valid BST, update information; 2) update max value on the fly;
*/
```