333 Largest BST Subtree

Given a binary tree, find the largest subtree which is a Binary Search Tree (BST), where largest means subtree with largest number of nodes in it.

Note: A subtree must include all of its descendants. Here's an example:

    10
    / \
   5  15
  / \   \ 
 1   8   7

The Largest BST Subtree in this case is the highlighted one.

The return value is the subtree's size, which is 3.

Follow up: Can you figure out ways to solve it with O(n) time complexity?

Solution 1: Brute Force

The Idea: Traverse every subtree and check to see if it follows a valid BST. This is true if the in order traversal is ordered. If the tree is unordered, the traversal will terminate back up the call stack with the maximum set as INT_MIN - as an intermediate sort of logic that will ensure the actually max will not update.

Complexity: O(n^2) time and O(n) space

void _getCountBST_subTree(TreeNode* root, int &cur_max, int &prev, bool &breakAll) {
    if (root && !breakAll) {
        _getCountBST_subTree(root->left, cur_max, prev, breakAll);
        if (root->val <= prev) {
            breakAll = true;
            cur_max = INT_MIN;
        }
        else {
            ++cur_max;
            prev = root->val;
        }
        _getCountBST_subTree(root->right, cur_max, prev, breakAll);
    }
}

void _traverseEverySubtree(TreeNode* root, int &the_max) {
    if (root) {
        int cur_max = 0;
        bool breakAll = false;
        int prev = INT_MIN;
        _getCountBST_subTree(root, cur_max, prev, breakAll);
        the_max = max(the_max, cur_max);
        _traverseEverySubtree(root->left, the_max);
        _traverseEverySubtree(root->right, the_max);
    }
}

int largestBSTSubtree(TreeNode *root) {
    int the_max = 0;
    _traverseEverySubtree(root, the_max);
    return the_max;
}

Solution 2: Linear

**Note: Leetcode doesn't allow me to modify the TreeNode datastructure, as I have done here, but this is a working solution.

The Idea: We explore the children first, so our algorithm will follow a post-order traversal. A leaf node is always a valid BST, otherwise we check for that left < root < right. So if it follows that the node is a BST, then we update the count of the root to be the sum of the count of it's left and right children. This process allows us accumulate the number of children through the tree. Initially the count for every node is set to 1 (as to be self-inclusive). As we accumulate these nodes, the absolute maximum number of valid BST nodes are updated. If the node is otherwise not in a valid place to be a BST, then the count is set to some really small number (working with a symbolic -infinity would be really nice). This will ensure that if the parent nodes are valid BST's but have invalid BST children, their count will not influence the abs_max.

Complexity: O(N) time, O(N) space

struct TreeNode {
    int val, count = 1;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

bool isBST(TreeNode *root) {
    bool leftValid = root->left ? root->val > root->left->val : true;
    bool rightValid = root->right ? root->val < root->right->val : true;
    return (leftValid && rightValid);
}

void _largestBSTSubtree(TreeNode *root, int &abs_max) {
    if (root) {
        _largestBSTSubtree(root->left, abs_max);
        _largestBSTSubtree(root->right, abs_max);
        if (isBST(root)) {
            root->count += root->left ? root->left->count : 0;
            root->count += root->right ? root->right->count : 0;
            abs_max = max(abs_max, root->count);
        }
        else
            root->count = -99999; // sufficiently minimal
                           // INT_MIN + INT_MIN = 2
    }
}

int largestBSTSubtree(TreeNode *root) {
    if (!root) return 0;
    else if (isLeaf(root)) return 1;

    int abs_max = 0;
    _largestBSTSubtree(root, abs_max);
    return abs_max;
}