PreviousNext
Coding/Dynamic programming

Count valid BST subtrees

Write codeHard30 min

Your task

Given a binary tree as a level-order array arr (null for missing), return the number of subtrees that are themselves valid binary search trees (BSTs). A single node counts as a BST. A subtree means a node together with ALL of its descendants. BST validity uses strict inequalities (left subtree values strictly less than the node, right subtree values strictly greater). 0 <= node count <= 20000.

Examples

count_bst_subtrees(arr: list[int]) -> int
Example 1
Inputcount_bst_subtrees([10, 5, 15, 1, 8, None, 7])
Output4