Tìm nút sâu nhất trong cây nhị phân C++

Cho cây nhị phân. Nhiệm vụ: tìm nút sâu nhất (deepest node) - nút ở độ sâu lớn nhất.

Ví dụ minh họa

Cây (hình ảnh): nút sâu nhất là 8.

Phương pháp 1: Duyệt in-order + theo dõi level O(n)

Đệ quy in-order, truyền currentLevel, cập nhật maxLevel và deepestNode khi currentLevel > maxLevel.

Phương pháp 2: Tính chiều cao + tìm nút ở level max O(n)

Tính height của cây. Duyệt lại cây, khi level == height thì in nút đó.

Ví dụ chương trình (Phương pháp 1)

#include <iostream> 
using namespace std; 

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

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

void findDeepestRec(Node* root, int level, int &maxLevel, int &deepestNode){
    if (!root) return;
    findDeepestRec(root->left, level + 1, maxLevel, deepestNode);
    if (level > maxLevel) { deepestNode = root->data; maxLevel = level; }
    findDeepestRec(root->right, level + 1, maxLevel, deepestNode);
}

int findDeepestNode(Node* root){
    int deepestNode = 0, maxLevel = 0;
    findDeepestRec(root, 0, maxLevel, deepestNode);
    return deepestNode;
}

int main(){
    Node* root = newNode(3);
    root->left = newNode(5); root->right = newNode(4);
    root->left->left = newNode(1); root->left->right = newNode(9);
    root->right->left = newNode(6); root->right->left->right = newNode(8);
    cout << "Nút sâu nhất: " << findDeepestNode(root);
    return 0;
}

Kết quả

Nút sâu nhất: 8