# Share my Java O(n) solution! Very easy to understand

• ``````public class Solution {
class Signal {
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
boolean flag = true;
int num = 0;
}
public int largestBSTSubtree(TreeNode root) {
// O(n) complexity
if (root == null) {
return 0;
}
Signal signal = helper(root);
return signal.num;
}
private Signal helper(TreeNode root) {
Signal signal = new Signal();
if (root == null) {
return signal;
} else if (root.left == null && root.right == null) {
signal.num = 1;
signal.min = root.val;
signal.max = root.val;
return signal;
}
Signal left = helper(root.left);
Signal right = helper(root.right);
if (left.flag == false || right.flag == false) {
signal.num = Math.max(left.num,right.num);
signal.flag = false;
return signal;
} else {
if (root.val > left.max && root.val < right.min) {
signal.min = Math.min(left.min,root.val);
signal.max = Math.max(right.max,root.val);
signal.num = left.num + right.num + 1;
return signal;
} else {
signal.num = Math.max(left.num, right.num);
signal.flag = false;
return signal;
}
}
}
}``````

• You can use num to replace the flag somehow.

• @monkeyGoCrazy Great solution. Here's a mildly refactored version of your code:

``````    static class Node {
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
boolean isBST = true;
int subtreeSize = 0;
}

public int largestBSTSubtree(TreeNode root) {
if (root == null) return 0;
Node node = dfs(root);
return node.subtreeSize;
}

private Node dfs(TreeNode root) {
Node node = new Node();
if (root == null) return node;
if (root.left == null && root.right == null) {
// leaf node
node.min = node.max = root.val; node.subtreeSize = 1;
return node;
}
Node left = dfs(root.left);
Node right = dfs(root.right);
if (!isBST(left, right, root)) {
node.isBST = false;
node.subtreeSize = Math.max(left.subtreeSize, right.subtreeSize);
} else {
node.subtreeSize = 1 + left.subtreeSize + right.subtreeSize;
node.min = Math.min(left.min, root.val); node.max = Math.max(right.max, root.val);
}
return node;
}

private boolean isBST(Node left, Node right, TreeNode root) {
return left.isBST && right.isBST && root.val >= left.max && root.val <= right.min;
}
``````

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