In anh em họ (cousin) của nút trong cây nhị phân C++

Cho cây nhị phân và một nút. In các anh em họ (cùng cấp, cha khác nhau). Ví dụ: nút 8 có anh em họ là 3, 7.

2 bước: Tìm cấp + In nút cùng cấp trừ anh em ruột

1. Hàm level(root, node, 1): trả về độ sâu của nút.
2. Hàm printCousin(root, node, level): ở cấp 2, bỏ qua nếu cha là cha của node. Cấp >2: đệ quy sang trái/phải.

Ví dụ minh họa

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

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

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

int getLevel(Node* root, Node* node, int lev) {
    if (!root) return 0;
    if (root == node) return lev;
    int l = getLevel(root->left, node, lev+1);
    return l ? l : getLevel(root->right, node, lev+1);
}

void printCousins(Node* root, Node* node, int lev) {
    if (!root || lev < 2) return;
    if (lev == 2) {
        if (root->left == node || root->right == node) return;
        if (root->left) cout << root->left->data << ' ';
        if (root->right) cout << root->right->data << ' ';
    } else {
        printCousins(root->left, node, lev-1);
        printCousins(root->right, node, lev-1);
    }
}

int main() {
    Node* root = newNode(11);
    root->left = newNode(15);
    root->right = newNode(4);
    root->left->left = newNode(3);
    root->left->right = newNode(7);
    root->left->right->right = newNode(9);
    root->right->left = newNode(17);
    root->right->right = newNode(8);
    root->right->left->right = newNode(5);
    
    cout << "Anh em ho cua nut 8: ";
    printCousins(root, root->right->right, getLevel(root, root->right->right, 1));
    return 0;
}

Kết quả

Anh em ho cua nut 8: 3 7