Another Casual Coder

I've tried this problem before, twice, with no luck. I remember trying an O(N)-time solution, but got wrong answers twice. Decided to go for an N^2 solution, this time it worked. Here is the problem: Largest BST Subtree - LeetCode

Input: root = [10,5,15,1,8,null,7]
Output: 3
Explanation: The Largest BST Subtree in this case is the highlighted one. The return value is the subtree's size, which is 3.

Input: root = [4,2,7,2,3,5,null,2,null,null,null,null,null,1]
Output: 2

The approach that I took was an N^2 one:

1/ Create a method that checks whether a given node is the root of a BST. Do it using post-order (in-order only really works if the tree contains only unique elements). This is an O(N)

2/ As part of (1), make it return the number of nodes in the subtree (no extra time added)

3/ Finally call it for each subnode in the tree. Another O(N)

Combined this would be O(N^2). Since N=10000, we're talking about 10^8. I thought it was going to time out - it didn't. Code is below, cheers, ACC.

public int LargestBSTSubtree(TreeNode root)
{
 int retVal = 0;
 LargestBSTSubtree(root, ref retVal);
 return retVal;
}
private void LargestBSTSubtree(TreeNode node, ref int maxNodes)
{
 if (node == null) return;
 int max = Int32.MinValue;
 int min = Int32.MaxValue;
 int numberNodes = 0;
 if (IsBST(node, ref max, ref min, ref numberNodes))
 {
 maxNodes = Math.Max(maxNodes, numberNodes);
 }
 LargestBSTSubtree(node.left, ref maxNodes);
 LargestBSTSubtree(node.right, ref maxNodes);
}
private bool IsBST(TreeNode node, ref int max, ref int min, ref int numberNodes)
{
 if (node == null) return true;
 int leftMax = Int32.MinValue;
 int leftMin = Int32.MaxValue;
 int leftNumberNodes = 0;
 if (!IsBST(node.left, ref leftMax, ref leftMin, ref leftNumberNodes)) return false;
 int rightMax = Int32.MinValue;
 int rightMin = Int32.MaxValue;
 int rightNumberNodes = 0;
 if (!IsBST(node.right, ref rightMax, ref rightMin, ref rightNumberNodes)) return false;
 if (leftMax>= node.val) return false;
 if (rightMin <= node.val) return false; max = node.val; max = Math.Max(max, leftMax); max = Math.Max(max, rightMax); min = node.val; min = Math.Min(min, leftMin); min = Math.Min(min, rightMin); numberNodes = 1 + leftNumberNodes + rightNumberNodes; return true; }