Largest BST Subtree in a Binary Tree

Given a binary tree, find the size of the largest subtree that is a Binary Search Tree (BST). A BST is defined as a binary tree in which for every node, all nodes in its left subtree have values less than the node’s value, and all nodes in its right subtree have values greater than the node’s value. Formally, for any node with value \(x\), if \(L\) is the maximum value in its left subtree and \(R\) is the minimum value in its right subtree, then the BST property holds if and only if \(L < x < R\).

You are given a binary tree represented in level-order format. The tree might contain missing nodes, which are represented by the string null. Your task is to compute and output the size (i.e. the number of nodes) of the largest subtree that is a BST.

Note: The tree nodes are defined by the structure of a typical binary tree. Use a post-order traversal to compute the validity and sizes of the BST subtrees.

inputFormat

The input is provided via standard input (stdin) as a single line containing the level-order traversal of a binary tree. The values are separated by spaces, and missing nodes are represented by the word null.

For example: 10 5 15 1 8 null 7

outputFormat

Output a single integer to standard output (stdout) representing the size of the largest subtree that is a BST.

10 5 15 1 8 null 7

3