# Java sol with explanation having O(n) runtime

• This approach takes some idea from the solution of Validate if BST problem.

``````    public int largestBSTSubtree(TreeNode root) {
int[] result = findSubtree(root);
return result == null ? 0 : result[0];
}

private int[] findSubtree(TreeNode node) {
// Base case
if (node == null) {
return null;
}

int[] leftChild = findSubtree(node.left);
int[] rightChild = findSubtree(node.right);

int leftChildVal = node.left == null ? Integer.MIN_VALUE : node.left.val;
int rightChildVal = node.right == null ? Integer.MAX_VALUE : node.right.val;

// initializing the min left and max right of subtree for the current node same as root
int leftMin = node.val, rightMax = node.val;

// initializing the left subtree node and right subtree nodes for the currrent node as 0
int leftNodes = 0, rightNodes = 0;

// checking immidiate child nodes
boolean isBinaryNode = leftChildVal <= node.val && rightChildVal > node.val;

if(leftChild != null){
// checking if max right of left node is less than current node and left node has a BST subtree
isBinaryNode = isBinaryNode && leftChild[2] < node.val && leftChild[3] == 1;
// assigning acutal left min for the current node
leftMin = leftChild[1];
// assigning acutal node count of left subtree
leftNodes = leftChild[0];
}

if(rightChild != null){
// checking if min left of right node is greater than current node and right node has a BST subtree
isBinaryNode = isBinaryNode && rightChild[1] > node.val && rightChild[3] == 1;
// assigning acutal right max for the current node
rightMax = rightChild[2];
// assigning acutal node count of right subtree
rightNodes = rightChild[0];
}

if (isBinaryNode) {
return new int[] { leftNodes + rightNodes + 1, leftMin, rightMax, 1 };
}

// if no longer BST is followed
return new int[] { Math.max(leftNodes, rightNodes), leftMin, rightMax, 0 };
}
``````

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