Short and clear JavaScript solution using DFS


  • 0
    var largestBSTSubtree = function(root, res = { val: 0 }) {
        if (!root) return 0;
        res.val = Math.max(res.val, BSTSize(root));
        largestBSTSubtree(root.left, res);
        largestBSTSubtree(root.right, res);
        return res.val;
    };
    
    function BSTSize(root, min = -Infinity, max = Infinity) {
        if (!root) return -1;
        if (root.val <= min || root.val >= max) return 0;
        const left = BSTSize(root.left, min, root.val);
        const right = BSTSize(root.right, root.val, max);
        return left && right ? 1 + (left > 0) * left + (right > 0) * right : 0;
    }
    

    The BSTSize of an invalid subtree is 0. Treat null nodes as -1 but don't count them as contributing to BST size.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.