You are given an arbitrary binary tree. A subtree here means a node together with all of its descendants. Return the number of nodes in the largest subtree that is a valid binary search tree with strict ordering (every left-subtree value smaller than the node, every right-subtree value larger). Return 0 for an empty tree.
Examples
10
/ \
5 15
/ \ \
1 8 7
Input: root = build_tree([10, 5, 15, 1, 8, None, 7])
Output: 3 (the subtree rooted at 5; 7 breaks the order under 15)
3
/ \
2 4
/
1
Input: root = build_tree([3, 2, 4, None, None, 1])
Output: 2 (4 with its left child 1; the whole tree fails because 1 < 3 sits on the right)
Constraints
0 <= number of nodes <= 3000- Values are integers (repeats possible; a repeat anywhere inside a subtree makes it invalid)
- O(n) time
Goals
- Combine child summaries (valid, size, min, max) in one postorder pass
- Treat a subtree as a node together with all of its descendants