Largest BST Subtree
Given a binary tree, find the largest subtree which is a Binary Search Tree (BST), where largest means subtree with largest number of nodes in it.
public int largestBSTSubtree(TreeNode root) {
helper(root);
return maxSubTree;
}
private int maxSubTree = 0;
private SubTreeInfo helper(TreeNode root){
if(root == null) return null;
SubTreeInfo leftTreeInfo = helper(root.left),
rightTreeInfo = helper(root.right);
SubTreeInfo currNodeInfo = new SubTreeInfo(root.val, root.val);
boolean isBST = true;
if(leftTreeInfo != null){
if(leftTreeInfo.max < root.val && leftTreeInfo.count != -1){
currNodeInfo.min = leftTreeInfo.min;
currNodeInfo.count += leftTreeInfo.count;
}else isBST = false;
}
if(rightTreeInfo != null){
if(rightTreeInfo.min > root.val && rightTreeInfo.count != -1){
currNodeInfo.max = rightTreeInfo.max;
currNodeInfo.count += rightTreeInfo.count;
}else isBST = false;
}
if(!isBST){
currNodeInfo.count = -1;
}else maxSubTree = Math.max(maxSubTree, currNodeInfo.count);
return currNodeInfo;
}
class SubTreeInfo{
int count = 1;
int max;
int min;
SubTreeInfo(int max, int min){
this.max = max;
this.min = min;
}
}