In tổ tiên của nút trong cây nhị phân C++

Cho cây nhị phân và một nút mục tiêu. In tất cả tổ tiên của nút đó (các nút trên đường từ gốc đến nút). Sử dụng đệ quy: nếu tìm thấy nút trong cây con trái hoặc phải, in nút hiện tại.

Đệ quy đơn giản

Hàm trả về true nếu tìm thấy nút mục tiêu trong cây con. Khi true, in giá trị nút hiện tại.

Ví dụ minh họa

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node *left, *right;
};

bool printAncestors(Node* root, int target) {
    if (!root) return false;
    if (root->data == target) return true;
    
    if (printAncestors(root->left, target) || printAncestors(root->right, target)) {
        cout << root->data << ' ';
        return true;
    }
    return false;
}

Node* newNode(int d) {
    Node* n = new Node();
    n->data = d; n->left = n->right = NULL;
    return n;
}

int main() {
    Node* root = newNode(10);
    root->left = newNode(6);
    root->right = newNode(13);
    root->left->left = newNode(3);
    root->left->right = newNode(8);
    root->right->left = newNode(12);
    
    cout << "To tien cua nut 8: ";
    printAncestors(root, 8);
    return 0;
}

Kết quả

To tien cua nut 8: 6 10