Viết chương trình tìm chiều cao tối đa của cây C++

Trong bài toán này, cho một cây nhị phân. Nhiệm vụ là viết chương trình tìm chiều cao (height) tối đa của cây.

Ví dụ:

Chiều cao cây là 3.

Để tìm chiều cao: kiểm tra chiều cao cây con trái và phải, lấy max của hai bên + 1. Đệ quy tiếp tục đến nút lá.

Ví dụ minh họa

#include <iostream>
using namespace std;

class node {
public:
    int data;
    node* left;
    node* right;
};

int height(node* node) {
    if (node == NULL)
        return 0;
    else {
        int lDepth = height(node->left);
        int rDepth = height(node->right);
        if (lDepth > rDepth)
            return lDepth + 1;
        else
            return rDepth + 1;
    }
}

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

int main() {
    node* root = insertNode(4);
    root->left = insertNode(5);
    root->right = insertNode(0);
    root->left->left = insertNode(1);
    root->left->right = insertNode(9);
    
    cout << "Chiều cao cây nhị phân: " << height(root);
    return 0;
}

Kết quả

Chiều cao cây nhị phân: 3