size of a BST in a BINARY TREE
//SIZE OF A BINARY SEARCH TREE IN BINARY TREE
public class SizeOfBSTinBT {
public static class Node {
int data;
Node left, right;
Node(int data) {
this.data = data;
}
}
public static class Info {
boolean isBST;
int size;
int min;
int max;
public Info(boolean isBST, int size, int min, int max) {
this.isBST = isBST;
this.size = size;
this.min = min;
this.max = max;
}
}
public static int maxBST = 0;
public static Info largestBST(Node root) {
if (root == null) {
return new Info(true, 0, Integer.MAX_VALUE, Integer.MIN_VALUE);
}
Info leftinfo = largestBST(root.left);
Info rightInfo = largestBST(root.right);
int size = leftinfo.size + rightInfo.size + 1;
int min = Math.min(root.data, Math.min(leftinfo.min, rightInfo.min));
int max = Math.max(root.data, Math.max(leftinfo.max, rightInfo.max));
if (root.data <= leftinfo.max || root.data >= rightInfo.min) {
return new Info(false, size, min, max);
}
if (leftinfo.isBST && rightInfo.isBST) {
maxBST = Math.max(maxBST, size);
return new Info(true, size, min, max);
}
return new Info(false, size, min, max);
}
public static void main(String[] args) {
Node root = new Node(50);
root.left = new Node(30);
root.left.left = new Node(5);
root.left.right = new Node(20);
root.right = new Node(60);
root.right.left = new Node(45);
root.right.right = new Node(70);
root.right.right.left = new Node(65);
root.right.right.right = new Node(80);
Info info = largestBST(root);
System.out.println("The max size of BST is: " + maxBST);
}
}
Comments
Post a Comment