Leetcode 333 Solution

This article provides solution to leetcode question 333 (largest-bst-subtree)
Categories:
Tags:
Access this page by simply typing in "lcs 333" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/largest-bst-subtree

Solution

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    int res = 0;

public:
    bool largestBSTSubtree(TreeNode* root, int& min_val, int& max_val, int& size)
    {
        if (root == NULL)
        {
            size = 0;
            max_val = INT_MIN;
            min_val = INT_MAX;
            return true;
        }

        int left_size, left_min, left_max;
        bool left_bst = largestBSTSubtree(root->left, left_min, left_max, left_size);

        int right_size, right_min, right_max;
        bool right_bst = largestBSTSubtree(root->right, right_min, right_max, right_size);

        size = 1 + left_size + right_size;

        bool valid = (left_max < root->val && root->val < right_min) && left_bst && right_bst;

        if (valid)
            res = max(size, res);

        min_val = root->val;
        min_val = min(min_val, left_min);
        min_val = min(min_val, right_min);

        max_val = root->val;
        max_val = max(root->val, left_max);
        max_val = max(root->val, right_max);

        return valid;
    }

    int largestBSTSubtree(TreeNode* root) {
        int size = 0;
        int min_val, max_val;
        largestBSTSubtree(root, min_val, max_val, size);
        return res;
    }
};