Tìm tất cả cặp có tổng cho trước trong BST C++

Cho cây nhị phân tìm kiếm (BST) và số target. Tìm **tất cả** cặp node có tổng bằng target. Sử dụng 2 stack (hoặc vector) mô phỏng duyệt in-order từ trái (tăng dần) và từ phải (giảm dần) – kỹ thuật two pointers trên BST.

Phương pháp

• Hai con trỏ current_left (đi trái) và current_right (đi phải).
• Hai vector làm stack: left_nodes, right_nodes.
• Lặp: đẩy hết trái vào left_nodes, hết phải vào right_nodes.
• Lấy node cuối mỗi stack: left_val, right_val.
• Nếu left_val >= right_val → dừng.
• Nếu tổng < target → pop left, đi phải node left.
• Nếu tổng > target → pop right, đi trái node right.
• Nếu bằng → in cặp, pop cả hai, đi phải left và trái right.

Ví dụ mã nguồn

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node *left, *right;
    Node(int d) : data(d), left(nullptr), right(nullptr) {}
};

Node* insert(Node* root, int data) {
    if (!root) return new Node(data);
    if (data < root->data) root->left = insert(root->left, data);
    else if (data > root->data) root->right = insert(root->right, data);
    return root;
}

void findPairs(Node* root, int target) {
    vector leftS, rightS;
    Node *curL = root, *curR = root;
    while (curL || curR || (!leftS.empty() && !rightS.empty())) {
        while (curL) { leftS.push_back(curL); curL = curL->left; }
        while (curR) { rightS.push_back(curR); curR = curR->right; }
        Node *l = leftS.back(), *r = rightS.back();
        int lv = l->data, rv = r->data;
        if (lv >= rv) break;
        if (lv + rv < target) { leftS.pop_back(); curL = l->right; }
        else if (lv + rv > target) { rightS.pop_back(); curR = r->left; }
        else {
            cout << lv << ' ' << rv << '\n';
            leftS.pop_back(); rightS.pop_back();
            curL = l->right; curR = r->left;
        }
    }
}

int main() {
    Node* root = nullptr;
    root = insert(root, 25);
    root = insert(root, 20);
    root = insert(root, 30);
    root = insert(root, 15);
    root = insert(root, 21);
    root = insert(root, 19);
    root = insert(root, 31);
    findPairs(root, 50); // 19 31, 20 30
    return 0;
}

Kết quả

19 31
20 30

Phức tạp O(n) thời gian, O(h) không gian (h = chiều cao cây).