Find the Largest Search-Tree Piece Inside a Tree
Implement largestBstSize
You are given the root of a binary tree that is not necessarily a search tree. A subtree (a node together with all its descendants) is a valid binary search tree if, at every node in it, all values in the left part are strictly smaller and all values in the right part strictly larger than the node's value. Return the number of nodes in the largest subtree that is a valid binary search tree.
Checking every subtree separately repeats a lot of work. One bottom-up pass in which each subtree reports whether it is a search tree, its size, and its smallest and largest values gives the answer in linear time.
Example 1:
Input: root = [50,30,60,20,40,45,70,10,25]
Output: 5
Example 2:
Input: root = [8,4,12,2,6,10,14]
Output: 7
Example 3:
Input: root = [5,5]
Output: 1
+ 13 hidden test cases run on Submit.
Constraints:
- ●
0 ≤ number of nodes ≤ 100; −1000 ≤ node.val ≤ 1000; values may repeat - ●
The tree is a general binary tree given by its root node (null for an empty tree); it does NOT have to be a search tree - ●
A subtree is a node together with ALL of its descendants. It is a valid binary search tree when for every node in it, all values in its left part are strictly smaller and all values in its right part are strictly larger - ●
Return the number of nodes in the LARGEST subtree of the tree that is a valid binary search tree (a single node always qualifies; an empty tree gives 0)
root =