package coding4fun;

/**
 * Find the maximum binary search subtree from a given binary tree.
 *
 * <pre>
 * Input:
 *       1
 *      / \
 *     5   3
 *    / \   \
 *   2   9   8
 *      / \
 *     7  12
 *    / \   \
 *   10  9  13
 *  /       /
 * 6       15
 *        /  \
 *       4   18
 *
 * Output: 3
 *         subtree: 15
 *                 /  \
 *                4   18
 * </pre>
 */
public class Problem39 {
    private static class Node {
        private final int value;
        private Node left;
        private Node right;

        private Node(int value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return Integer.toString(value);
        }
    }

//    private static class Group {
//        private int group;
//    }
//
//    private static int maxBST(Node root) {
//        Map<Integer, Integer> groupCount = new HashMap<>();
//        maxBST(root, new Group(), groupCount, 0);
//        System.out.println(groupCount);
//        return 0;
//    }
//
//    private static void maxBST(Node node, Group group, Map<Integer, Integer> groupCount,
//                               int groupNumber) {
//        if (node == null) {
//            return;
//        }
//        int newGroupNumber = groupNumber;
//        int leftGroupNumber = newGroupNumber;
//        int rightGroupNumber = newGroupNumber;
//        if (node.left != null && node.right != null) {
//            if (node.left.value < node.value && node.value < node.right.value) {
//                if (!groupCount.containsKey(newGroupNumber)) {
//                    System.out.println("root both: " + node + ", group: " + newGroupNumber);
//                    groupCount.put(newGroupNumber, 2);
//                } else {
//                    groupCount.put(newGroupNumber, groupCount.get(newGroupNumber) + 2);
//                }
//            } else {
//                leftGroupNumber = group.group++;
//                rightGroupNumber = group.group++;
//            }
//        } else if (node.left != null) {
//            if (node.left.value < node.value) {
//                if (!groupCount.containsKey(newGroupNumber)) {
//                    System.out.println("root left: " + node + ", group: " + newGroupNumber);
//                    groupCount.put(newGroupNumber, 1);
//                } else {
//                    groupCount.put(newGroupNumber, groupCount.get(newGroupNumber) + 1);
//                }
//            } else {
//                leftGroupNumber = group.group++;
//            }
//        } else if (node.right != null) {
//            if (node.value < node.right.value) {
//                if (!groupCount.containsKey(newGroupNumber)) {
//                    System.out.println("root right: " + node + ", group: " + newGroupNumber);
//                    groupCount.put(newGroupNumber, 1);
//                } else {
//                    groupCount.put(newGroupNumber, groupCount.get(newGroupNumber) + 1);
//                }
//            } else {
//                rightGroupNumber = group.group++;
//            }
//        }
//        maxBST(node.left, group, groupCount, leftGroupNumber);
//        maxBST(node.right, group, groupCount, rightGroupNumber);
//    }

    private static int maxBST(Node root) {
        if (isBST(root)) {
            return size(root);
        }
        return Math.max(maxBST(root.left), maxBST(root.right));
    }

    private static int size(Node root) {
        if (root == null) {
            return 0;
        }
        return size(root.left) + size(root.right) + 1;
    }

    private static boolean isBST(Node root) {
        return isBST(root, new PrevNode(Integer.MIN_VALUE));
    }

    private static class PrevNode {
        private int value;

        private PrevNode(int value) {
            this.value = value;
        }
    }

    private static boolean isBST(Node node, PrevNode prev) {
        if (node == null) {
            return true;
        }
        boolean a = isBST(node.left, prev);
        if (prev.value > node.value) {
            return false;
        }
        prev.value = node.value;
        boolean b = isBST(node.right, prev);
        return a & b;
    }

    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(5);
        root.left.left = new Node(2);
        root.left.right = new Node(9);
        root.left.right.left = new Node(7);
        root.left.right.right = new Node(12);
        root.left.right.left.left = new Node(10);
        root.left.right.left.right = new Node(9);
        root.left.right.left.left.left = new Node(6);
        root.left.right.right.right = new Node(13);
        root.left.right.right.right.left = new Node(15);
        root.left.right.right.right.left.left = new Node(4);
        root.left.right.right.right.left.right = new Node(18);
        root.right = new Node(3);
        root.right.right = new Node(8);

        System.out.println(maxBST(root));
    }
}

@@ -729,2528 +729,8 @@
  %7D%0A%0A
-//    private static class Group %7B%0A//        private int group;%0A//    %7D%0A//%0A//    private static int maxBST(Node root) %7B%0A//        Map%3CInteger, Integer%3E groupCount = new HashMap%3C%3E();%0A//        maxBST(root, new Group(), groupCount, 0);%0A//        System.out.println(groupCount);%0A//        return 0;%0A//    %7D%0A//%0A//    private static void maxBST(Node node, Group group, Map%3CInteger, Integer%3E groupCount,%0A//                               int groupNumber) %7B%0A//        if (node == null) %7B%0A//            return;%0A//        %7D%0A//        int newGroupNumber = groupNumber;%0A//        int leftGroupNumber = newGroupNumber;%0A//        int rightGroupNumber = newGroupNumber;%0A//        if (node.left != null && node.right != null) %7B%0A//            if (node.left.value %3C node.value && node.value %3C node.right.value) %7B%0A//                if (!groupCount.containsKey(newGroupNumber)) %7B%0A//                    System.out.println(%22root both: %22 + node + %22, group: %22 + newGroupNumber);%0A//                    groupCount.put(newGroupNumber, 2);%0A//                %7D else %7B%0A//                    groupCount.put(newGroupNumber, groupCount.get(newGroupNumber) + 2);%0A//                %7D%0A//            %7D else %7B%0A//                leftGroupNumber = group.group++;%0A//                rightGroupNumber = group.group++;%0A//            %7D%0A//        %7D else if (node.left != null) %7B%0A//            if (node.left.value %3C node.value) %7B%0A//                if (!groupCount.containsKey(newGroupNumber)) %7B%0A//                    System.out.println(%22root left: %22 + node + %22, group: %22 + newGroupNumber);%0A//                    groupCount.put(newGroupNumber, 1);%0A//                %7D else %7B%0A//                    groupCount.put(newGroupNumber, groupCount.get(newGroupNumber) + 1);%0A//                %7D%0A//            %7D else %7B%0A//                leftGroupNumber = group.group++;%0A//            %7D%0A//        %7D else if (node.right != null) %7B%0A//            if (node.value %3C node.right.value) %7B%0A//                if (!groupCount.containsKey(newGroupNumber)) %7B%0A//                    System.out.println(%22root right: %22 + node + %22, group: %22 + newGroupNumber);%0A//                    groupCount.put(newGroupNumber, 1);%0A//                %7D else %7B%0A//                    groupCount.put(newGroupNumber, groupCount.get(newGroupNumber) + 1);%0A//                %7D%0A//            %7D else %7B%0A//                rightGroupNumber = group.group++;%0A//            %7D%0A//        %7D%0A//        maxBST(node.left, group, groupCount, leftGroupNumber);%0A//        maxBST(node.right, group, groupCount, rightGroupNumber);%0A//    %7D%0A%0A
     

Update problem 39