LC: Largest BST Subtree - spiralgo/algorithms GitHub Wiki

The Essence:

First and foremost, one should recall what it means to have a tree that qualifies to be a binary search tree. For a simple recursive definition, a binary search tree has its root being parent of two binary search tree roots and this root's value is larger* than all values in the tree of its left child and smaller* than all the values in the tree of its right child.

If these conditions are satisfied, the size of the BST here is the sizes of the left subtree and the right subtree + 1 (the root itself). If the conditions are not met, otherwise, it would be the maximum of the either two subtree, whether they themselves are binary search tree or they simply contain one of that size.

Then we simply need to recurse our way up through the leaves to the root node, bringing 3 values with us:

The minimum value in this subtree
The maximum value in this subtree
The maximum size of a binary search tree within this subtree

*or in some cases also equal, but we consider such a case invalid here

Details:

Additionally, if a subtree is not a BST, then a simple inversion/negation can have all the parent subtrees be invalid: We can set the minimum value to positive infinity and the maximum value to negative infinity.

The procedure above is naturally post-order recursive. The code can be found here: https://github.com/spiralgo/algorithms/blob/master/src/main/java/algorithms/curated170/medium/LargestBSTSubtree.java