หา BST Subtree ใหญ่ที่สุดใน Binary Tree ใน C++ (Set 1)

ในปัญหานี้ เราได้รับ Binary Tree งานคือหา BST (Binary Search Tree) subtree ที่มีขนาดใหญ่ที่สุด

BST Properties

• Left subtree values < Root value
• Right subtree values >= Root value

ตัวอย่าง

Output: 3 (Full tree is BST)

วิธีที่ 1: Naive O(N²) - Check ทุก Node

Inorder traversal + ตรวจสอบทุก node ว่า subtree เป็น BST หรือไม่

int findTreeSize(Node* node) {
    if (!node) return 0;
    return findTreeSize(node->left) + findTreeSize(node->right) + 1;
}

bool isBST(Node* node) {
    if (!node) return true;
    if (node->left && node->left->data > node->data) return false;
    if (node->right && node->right->data < node->data) return false;
    return isBST(node->left) && isBST(node->right);
}

int findLargestBST(Node* root) {
    if (isBST(root)) return findTreeSize(root);
    return max(findLargestBST(root->left), findLargestBST(root->right));
}

วิธีที่ 2: Bottom-Up O(N) - Optimal

Traverse จากใบขึ้นมา เก็บข้อมูลต่อ node:

• Is BST?
• Min value ใน subtree
• Max value ใน subtree
• Size ของ BST ใหญ่ที่สุดที่เจอ

int largestBSTSizeRec(Node* node, int* minVal, int* maxVal, int* maxSize, bool* isBST) {
    if (!node) { *isBST = true; return 0; }
    
    int min = INT_MAX;
    bool leftFlag = false, rightFlag = false;
    int leftSize = largestBSTSizeRec(node->left, minVal, maxVal, maxSize, isBST);
    if (*isBST && node->data > *maxVal) leftFlag = true;
    
    min = *minVal; *minVal = INT_MAX;
    int rightSize = largestBSTSizeRec(node->right, minVal, maxVal, maxSize, isBST);
    if (*isBST && node->data < *minVal) rightFlag = true;
    
    if (min < *minVal) *minVal = min;
    *minVal = min(*minVal, node->data);
    *maxVal = max(*maxVal, node->data);
    
    if (leftFlag && rightFlag) {
        int currSize = leftSize + rightSize + 1;
        *maxSize = max(*maxSize, currSize);
        return currSize;
    }
    *isBST = false;
    return 0;
}

ผลลัพธ์

Size of largest BST is 5