ตรวจสอบอาร์เรย์ว่าเป็น Preorder Traversal ของ BST ได้หรือไม่ใน C++

ปัญหา

ให้ลำดับตัวเลข ตรวจสอบว่าลำดับนี้เป็น Preorder Traversal ของ Binary Search Tree (BST) ใดๆ ได้หรือไม่

Preorder: Root → Left → Right

BST property: Left subtree < Root < Right subtree

ตัวอย่าง

Preorder: [40, 30, 35, 80, 100]

BST ที่สอดคล้อง:

      40
     /  \
   30    80
     \     \
     35    100

อัลกอริทึม: Stack-based O(n)

ใช้ stack จำลองการท่อง Preorder:

1. root = -∞ (ค่าต่ำสุด)
2. สำหรับแต่ละค่าใน preorder:
   • ถ้า value < root → ผิด (violate BST property)
   • Pop stack จนกว่าจะว่างหรือ top ≥ value, อัปเดต root = popped value
   • Push value ลง stack
3. จบลูป → ถูกต้อง

เหตุผล

ใน Preorder ของ BST:

• ค่าจะเพิ่มขึ้นเมื่อเข้าสู่ right subtree
• เมื่อเจอค่าที่มากกว่า stack top → หมายถึงกำลังขึ้นไป right subtree ของ ancestor
• ค่า root ที่ pop ออกคือ lower bound สำหรับค่าต่อไป

ตัวอย่างโค้ด C++

#include <iostream>
#include <stack>
#include <vector>
#include <climits>
using namespace std;

bool isValidPreorder(const vector<int>& pre) {
    stack<int> st;
    int root = INT_MIN;
    
    for (int value : pre) {
        if (value < root) return false;
        
        while (!st.empty() && st.top() < value) {
            root = st.top();
            st.pop();
        }
        st.push(value);
    }
    return true;
}

int main() {
    vector<int> pre1 = {40, 30, 35, 80, 100};
    vector<int> pre2 = {40, 30, 35, 20, 80, 100}; // 20 < 35 (root) → invalid
    
    cout << "Pre1: " << (isValidPreorder(pre1) ? "Valid BST preorder" : "Invalid") << endl;
    cout << "Pre2: " << (isValidPreorder(pre2) ? "Valid BST preorder" : "Invalid") << endl;
    
    return 0;
}

ผลลัพธ์

Pre1: Valid BST preorder
Pre2: Invalid

การทำงานทีละขั้น (Pre1)

ความซับซ้อน

• เวลา: O(n) - แต่ละค่า push/pop สูงสุด 1 ครั้ง
• พื้นที่: O(n) - stack