# Easy to understand Java Divide & Conquer Solution

• ``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Pair {
public int val;
public boolean isValid;
int min;
int max;
public Pair(int val, boolean b, int m, int n){
this.val = val;
this.isValid = b;
min = m;
max = n;
}
}
public class Solution {
int res = 0;
int m = Integer.MAX_VALUE;
int n = Integer.MIN_VALUE;
public int largestBSTSubtree(TreeNode root) {
//should be a binary search tree
if(root == null) return 0;
return helper(root, false).val;
}
private Pair helper(TreeNode root, boolean isValid) {
if(root == null) return new Pair(0, false, m, n);
if(root.left == null && root.right == null) return new Pair(1, true, root.val, root.val);

Pair left = helper(root.left, false);
Pair right = helper(root.right, false);

Pair res = new Pair(0, false, root.val, root.val);

if(root.left != null && root.right != null) {
if(root.val > root.left.val && root.val < root.right.val && left.isValid && right.isValid && left.max < root.val && right.min > root.val) {
res.val = left.val + right.val + 1;
res.isValid = true;
res.max = right.max;
res.min = left.min;
}else{
res.val = Math.max(left.val, right.val);
res.isValid = false;
}
}
if(root.left == null) {
if(root.val < root.right.val && right.isValid && right.min > root.val) {
res.val = right.val + 1;
res.isValid = true;
res.min = root.val;
res.max = right.max;
}else {
res.val = Math.max(1, right.val);
res.isValid = false;
}
}
if(root.right == null) {
if(root.val > root.left.val && left.isValid && left.max < root.val) {
res.val = left.val + 1;
res.isValid = true;
res.max = root.val;
res.min = left.min;
}else {
res.val = Math.max(1, left.val);
res.isValid = false;
}
}
return res;
}
}``````

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