# Java 1ms O(n) bottom-up solution without using arrays. (recursion)

• Key points:

1. Using a global variable to store the max count, so don't need the count the total node after finding the BST subtree. 2. To make each recursion has the starting condition of min < root.val < max, the function checks the child node's value first before calling the next recursion. In addition, the null nodes can be avoided.

public class Solution {
int res = 0; // store the max count of BST nodes
int helper(TreeNode root, long min, long max) {
if ( root == null ) return 0;
long value = (long) root.val;
int left = 0; // store left size's BST nodes. If -1, not a BST root.
int right = 0; // store right size's BST nodes. If -1, not a BST root.
boolean out_of_range = false;
// if one of the child nodes is out of the range,
// than the previous node is not a root of BST
if ( root.left != null ) {
long lv = (long) root.left.val;
if ( lv > value ) {
// current node is not a root of BST, reset both ends
helper(root.left, Long.MIN_VALUE, Long.MAX_VALUE);
left = -1;
out_of_range = true;
} else {
if ( lv < min) {
// previous node is not a root of BST, reset min value
left = helper(root.left, Long.MIN_VALUE, value);
out_of_range = true;
} else {
// previous node is possible to be a root of BST
left = helper(root.left, min, value);
}
}
}
if ( root.right != null ) {
long rv = (long) root.right.val;
if ( rv < value ) {
// current node is not a root of BST, reset both ends
helper(root.right, Long.MIN_VALUE, Long.MAX_VALUE);
right = -1;
out_of_range = true;
} else {
if ( rv > max) {
// previous node is not a root of BST, reset max value
right = helper(root.right, value, Long.MAX_VALUE);
out_of_range = true;
} else {
// previous node is possible to be a root of BST
right = helper(root.right, value, max);
}
}
}
if ( ( left >= 0 ) && ( right >= 0 ) ) {
// both child nodes are roots of BST
// and left.val < root.val < right.val
int ret = left+right+1; // count the total BST nodes
res = Math.max(res, ret); // record the maximun nodes
if ( ! out_of_range ) {
// pass the count back if the privious node is still in the range
return ret;
}
}
return -1;
}
public int largestBSTSubtree(TreeNode root) {
helper(root, Long.MIN_VALUE, Long.MAX_VALUE);
return res;
}
}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.