Largest BST Subtree
Medium · Binary Search Trees · about 25 minutes
Asked at Microsoft, Amazon, Google, Meta, Bloomberg.
Among all subtrees of a binary tree (a subtree being a node plus everything below it), find the biggest one that is a valid binary search tree, with left values strictly smaller and right values strictly larger, and return how many nodes it has.