gauravonics
BAN USERLets divide this to sub problems.
1. Given a binary tree find out if its a BST. -- isTreeBST()
2. Given a tree find total number of nodes -- getTotalObjects()
3. Finally find larget BST using recusrion - getLargestBST().
Code :
public Tree<T> getLargestBST(){
if(isTreeBST())return this;
else {int l = 0;
if(lTree!=null){
l = lTree.getLargestBST().getTotalObjects();
}
int r = 0;
if(rTree!=null){
r = rTree.getLargestBST().getTotalObjects();
}
if(l>r) return lTree.getLargestBST();
else return rTree.getLargestBST();
}
}
public boolean isTreeBST(){
if(root == null) return true;
boolean l = true;
boolean r = true;
if(lTree != null) {
if(lTree.root.compareTo(root)<0) {
l = lTree.isTreeBST();
}else{
return false;
}
}
if(rTree != null) {
if(rTree.root.compareTo(root)>0) {
r = rTree.isTreeBST();
}else{
return false;
}
}
return l&&r;
}
public int getTotalObjects(){
int n = 0;
if(root!=null) n++;
if(lTree!=null){
n +=lTree.getTotalObjects();
}
if(rTree!=null){
n +=rTree.getTotalObjects();
}
return n;
}
- gauravonics January 29, 2014