Largest BST subtree

Posted on |

My c++ solution to this problem.

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.

When I first saw it, the method that check all the validate subtree in this tree is brute force and time complexity is O(pow(n,2)). Actually, we only need to pass the whole tree one time and remember the information that we need for their parents, since a subtree is not a BST, the subtree with parent node is neither. We can traverse the tree in DFS and return the info in a tuple.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int largestBSTSubtree(TreeNode* root) {
        int res = 0;
        dfs(root, res);
        return res;
    }
     inline auto dfs(TreeNode* root,int& maxVal) -> tuple<int,int,int,int>{
        if(!root) return {1,0,INT_MAX,INT_MIN};
        auto item_1 = dfs(root->left,maxVal);
        auto item_2 = dfs(root->right,maxVal);
        if (!get<0>(item_1) || !get<0>(item_2) || root->val <= get<3>(item_1) || root->val > get<2>(item_2)){
            return {0,0,0,0};
        }
        int maxNode = get<1>(item_1) + get<1>(item_2) + 1;
        maxVal = max(maxVal, maxNode);
        return {1,maxNode,min(root->val,get<2>(item_1)),max(root->val,get<3>(item_2))};     
    }
};

std::tuple is a new and flexible data struture likes std::pair, the different is we need to use std::get<> with explict template argument to access the elements in the tuple.