Find the largest BST in a Binary Tree

http://www.geeksforgeeks.org/find-the-largest-subtree-in-a-tree-that-is-also-a-bst/

Given a Binary Tree, write a function that returns the size of the largest subtree which is also a Binary Search Tree (BST). If the complete Binary Tree is BST, then return the size of whole tree.

1. public class FindLargestBST {
3.     public static Tree getTree(){
4.         Tree t50 = new Tree(50);
5.         Tree t30 = new Tree(30);
6.         Tree t60 = new Tree(60);
7.         Tree t5 = new Tree(5);
8.         Tree t20 = new Tree(20);
9.         Tree t45 = new Tree(45);
10.         Tree t70 = new Tree(70);
11.         Tree t65 = new Tree(65);
12.         Tree t80 = new Tree(80);
13.         t50.left = t30;
14.         t50.right = t60;
15.         t30.left = t5;
16.         t30.right = t20;
17.         t60.left = t45;
18.         t60.right = t70;
19.         t70.left = t65;
20.         t70.right = t80;
21.         return t50;
22.     }
24.     public static Tree getTree2(){
25.         Tree t1 = new Tree(1);
26.         Tree t2 = new Tree(2);
27.         Tree t3 = new Tree(3);
28.         Tree t4 = new Tree(4);
29.         Tree t5 = new Tree(5);
30.         t5.left = t2;
31.         t5.right = t4;
32.         t2.left = t1;
33.         t2.right = t3;
34.         return t5;
35.     }
36.     public static void findLargestBST(Tree tree, LargestBSTData data){
37.         if(tree==null){
38.             data.size = 0;
39.             data.isBST = true;
40.             data.tree = null;
41.             return;
42.         }
43.         LargestBSTData ldata = new LargestBSTData();
44.         LargestBSTData rdata = new LargestBSTData();
45.         findLargestBST(tree.left, ldata);
46.         findLargestBST(tree.right, rdata);
47.         //when left-subtree and right-subtree are both BST, check if tree is a BST.
48.         if(ldata.isBST&&rdata.isBST){
49.             boolean lBST = false;    //if left-subtree and tree can be treated as BST.
50.             boolean rBST = false;    //if right-subtree and tree can be treated as BST.
51.             if(tree.left==null||tree.left.value<tree.value){
52.                 lBST  = true;
53.             }
54.             if(tree.right==null||tree.right.value>tree.value){
55.                 rBST  = true;
56.             }
57.             if(lBST&&rBST){    //tree is a BST
58.                 data.size = ldata.size + rdata.size + 1;
59.                 data.tree = tree;
60.                 data.isBST = true;
61.                 return;
62.             }
63.         }
64.         //tree is not a BST
65.         data.size = ldata.size>rdata.size?ldata.size:rdata.size;
66.         data.tree = ldata.size>rdata.size?ldata.tree:rdata.tree;
67.         data.isBST = false;
68.     }
70.     public static void main(String[] args) {
71.         Tree tree = getTree();
72.         LargestBSTData data = new LargestBSTData();
73.         findLargestBST(tree, data);
74.         System.out.println(data.size);
75.     }
77. }
79. class LargestBSTData{
80.     public Tree tree;   //to indicate the largest BST of current tree
81.     public boolean isBST;    //to indicate if current tree is a BST
82.     public int size;   //to indicate the size of the largest BST of current tree
83. }