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