Largest BST subtree - Teeeeeebag/LeetCode GitHub Wiki

1. Mistake: I just look at a node's left and right children and compare their values to itself. That's not sufficient. You have to compare with max and min from their left and right children.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Tuple{
    public int min, max, cnt;
    public Tuple(){
        min = Integer.MAX_VALUE;
        max = Integer.MIN_VALUE;
        cnt = 0;
    }
}
public class Solution {
    private int maxLen = 0;
    private Tuple traversal(TreeNode n){
        if(n == null){
            return new Tuple();
        }
        Tuple left = traversal(n.left);
        Tuple right = traversal(n.right);
        if(left == null || right == null){
            return null;
        }
        if(left.max > n.val || right.min < n.val){
            return  null;
        }
        Tuple res = new Tuple();
        res.min = Math.min(n.val, left.min);
        res.max = Math.max(right.max, n.val);
        res.cnt = left.cnt+right.cnt+1;
        maxLen = Math.max(maxLen, res.cnt);
        return res;
    }
    public int largestBSTSubtree(TreeNode root) {
        traversal(root);
        return maxLen;
    }
}