440. Find the Largest BST Subtree in a Binary Tree

Given an arbitrary binary tree, find the largest subtree (by node count) that is itself a valid binary search tree, and print its size. The tree is given as space-separated level-order tokens, where 'N' means no node there: the first token is the root, then for each node dequeued in level order you read its left-child token then its right-child token (if input runs out early, remaining children are treated as N).

Input: A single line of space-separated level-order tokens describing the binary tree ('N' marks an absent child). Output: Print a single integer - the size of the largest subtree that is a valid BST.

1 <= number of nodes <= 10^5

The maximum valid BST subtree does NOT have to be the whole tree, and does NOT have to include the root - tracking a running best across every single node checked (not just returning the root's own result) is essential.

In a general (possibly non-BST) binary tree, find the largest subtree that happens to itself be a valid binary search tree. Brute force: For every single node, separately check if its ENTIRE subtree is a valid BST from scratch (re-traversing and re-validating each time) - this costs O(n²) in the worst case, since checking one subtree's validity can itself take O(subtree size). Optimised: A single post-order pass that returns THREE pieces of information per node (is this subtree a valid BST, and if so its min and max) lets each node's check reuse its children's already-computed results directly, with no re-traversal - this turns an O(n²) repeated-validation approach into a single O(n) bottom-up pass.

For every node in the tree, gather all values in its subtree, sort them, and check whether that sorted order matches the subtree's in-order traversal exactly (confirming both the BST property and that there are no duplicate-position issues); if it is a valid BST, record its size and keep the maximum seen. This checks the definition directly for every candidate subtree, but sorting each subtree's values from scratch adds an extra logarithmic factor on top of the already-repeated work of visiting every subtree independently. Time: O(n^2 log n) Space: O(n)

For every node, instead of sorting, validate whether its subtree is a BST using the linear-time recursive min/max bounds check (the same technique used for validating a whole tree), and if valid, count its nodes; track the largest such subtree found across all starting nodes. Dropping the sort removes the extra log factor from the brute approach, but the algorithm is still fundamentally re-examining every subtree from scratch as it walks up the tree, so it remains quadratic overall. Time: O(n^2) Space: O(h)

Do one post-order traversal where each node combines the results already computed for its children instead of re-scanning its subtree: each call returns whether the subtree is a BST, its size, and its minimum and maximum values. A node's subtree is a BST exactly when both children report BST subtrees and the node's value fits strictly between the left subtree's max and the right subtree's min; its size is then the sum of the children's sizes plus one. Because every node's contribution is computed exactly once from already-known child information, no subtree is ever revisited, collapsing the quadratic repeated work of the previous approaches into a single linear pass. Time: O(n) Space: O(h)

1. Process the tree bottom-up (post-order): for each node, determine whether its ENTIRE subtree is a valid BST, and if so, its min and max values (needed for the parent's own check). 2. A node's subtree is a valid BST exactly when both children's subtrees are valid BSTs, AND the node's value is greater than the left subtree's max and less than the right subtree's min. 3. Track the maximum VALID BST subtree size found at ANY node during this process, not just at the root - even if the whole tree fails, some sub-portion might still be the largest valid BST.

Time: O(n) - one single post-order pass, computing each node's validity/min/max exactly once. Space: O(h) for the recursion stack.

Test with a single-node tree (answer 1), a tree that is already entirely a valid BST (answer equals total node count), a tree where the largest valid BST subtree is smaller than the whole tree, and a tree with 10^5 nodes for performance.

Be ready to explain precisely WHAT information must be returned from each recursive call (validity, min, max, AND size) - forgetting to also propagate min/max upward is the most common way this problem's efficient solution goes wrong.