12. Largest BST Subtree

Link to the problem

Description

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.

Example

Input: [10,5,15,1,8,null,7], Output: 3

Idea

Recursively compute the number of nodes, whether the current tree is a BST, the size of the largest BST subtree in the current tree, min value, and max value.

Solution

class Solution {
private:
    // info[0] stores size of largest BST subtree
    // info[1] stores whether the tree is BST
    // info[2] stores size of current tree
    // info[3] stores min
    // info[4] stores max
    void largestBSTSubtreeHelper(TreeNode *root, vector<int> &info) {
        if (!root) {
            info.push_back(0);
            info.push_back(1);
            info.push_back(0);
            info.push_back(INT_MAX);
            info.push_back(INT_MIN);
        } else {
            vector<int> leftInfo, rightInfo;
            largestBSTSubtreeHelper(root->left, leftInfo);
            largestBSTSubtreeHelper(root->right, rightInfo);
            int currSize = 1 + leftInfo[2] + rightInfo[2];
            int currMin = min(root->val, min(leftInfo[3], rightInfo[3]));
            int currMax = max(root->val, max(leftInfo[4], rightInfo[4]));
            bool isBST = leftInfo[1] > 0 && rightInfo[1] > 0;
            if (root->val <= leftInfo[4] || root->val >= rightInfo[3]) isBST = false;
            int largestBST = isBST ? currSize : max(leftInfo[0], rightInfo[0]);
            info.push_back(largestBST);
            info.push_back(isBST ? 1 : 0);
            info.push_back(currSize);
            info.push_back(currMin);
            info.push_back(currMax);
        }
    }

public:
    int largestBSTSubtree(TreeNode* root) {
        vector<int> info;
        largestBSTSubtreeHelper(root, info);
        return info[0];
    }
};

73 / 73 test cases passed.
Runtime: 12 ms