Largest BST Inside a Tree

The tests write a tree as a level-order list (row by row, left to right) with None for a missing child: [3, 9, 20, None, None, 15, 7] is a root 3 with children 9 and 20, where 20 has children 15 and 7.

This tree is not necessarily a BST. Return the number of nodes in the largest subtree (a node together with all its descendants) that is a valid BST (left values strictly smaller, right values strictly larger).

For [10, 5, 15, 1, 8, None, 7] the answer is 3 (the subtree rooted at 5).

Examples

Example 1

Input:

largest_bst_subtree(root)  # root = [10, 5, 15, 1, 8, None, 7]

Output:

3

Example 2

Input:

largest_bst_subtree(root)  # root = [5, 4, 6, None, 3, 7, 8]

Output:

1

Constraints

• 0 <= number of nodes <= 100000
• The tree is not deeper than 800 levels.
• -10**9 <= val <= 10**9