Largest BST Size

• Time : O(n)
• Space : O(1)

class BinaryTree {
public:
  int value;
  BinaryTree *left;
  BinaryTree *right;

  BinaryTree(int value) {
    this->value = value;
    left = nullptr;
    right = nullptr;
  }
};

struct Sub {
    int mi, ma, count;
    bool valid;
};
int res;

Sub helper(BinaryTree* node) {
   if(!node->left and !node->right) {
       res = max(res, 1);
       return {node->value, node->value, 1, true};
   }
   if(node->left and node->right) {
       auto lsub = helper(node->left);
       auto rsub = helper(node->right);
       if(lsub.valid and rsub.valid and lsub.ma < node->value and node->value <= rsub.mi) {
           res = max(res, lsub.count + rsub.count + 1);
           return {lsub.mi, rsub.ma, lsub.count + rsub.count + 1, true};
       } else return {INT_MAX, INT_MIN, -1, false};
   }
   if(node->left) {
       auto lsub = helper(node->left);
       if(lsub.valid and lsub.ma < node->value) {
           res = max(res, lsub.count + 1);
           return {lsub.mi, node->value, lsub.count + 1, true};
       } else return {INT_MAX, INT_MIN, -1, false};
   }
   if(node->right) {
       auto rsub = helper(node->right);
       if(rsub.valid and node->value <= rsub.mi) {
           res = max(res, rsub.count + 1);
           return {node->value, rsub.ma, rsub.count + 1, true};
       } else return {INT_MAX, INT_MIN, -1, false};
   }
}

int largestBstSize(BinaryTree *tree) {
    res = -1;
    helper(tree);
    return res;
}